Opened 7 years ago

Closed 7 years ago

Last modified 2 weeks ago

#4154 closed bug (fixed)

Deadlock in Chan module

Reported by: NeilMitchell Owned by:
Priority: high Milestone: 8.4.1
Component: libraries/base Version: 6.12.3
Keywords: Cc: ndmitchell@…, mmitar@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Incorrect result at runtime Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by bgamari)

The following program:

module Main where

import Control.Concurrent

main :: IO ()
main = do
    todo <- newChan
    forkIO $ readChan todo
    putStrLn "Before isEmptyChan"
    b <- isEmptyChan todo
    putStrLn "After isEmptyChan"
    writeChan todo ()

Gives the output:

$ ghc --make Main.hs -threaded && ./Main.exe
Before isEmptyChan
Main.exe: thread blocked indefinitely in an MVar operation

I think that's a bug. Note that if the putStrLn statements are removed then it works, but I think that's because the printing introduces a delay that lets the other thread run.

Change History (12)

comment:1 Changed 7 years ago by simonmar

Milestone: 6.14.1
Operating System: WindowsUnknown/Multiple
Priority: normalhigh

I can't see a way to fix this in the implementation of Chan while retaining the properties and the other operations it has. The problem is that readChan holds empty the read end of the Chan, but isEmptyChan and unGetChan (see #3527) also need to take the read end, so they deadlock if there is a blocked reader on an empty Chan.

My suggestion is to deprecate both isEmptyChan and unGetChan, with a message explaining the problem and directing people to TChan instead. TChan works, but lacks the fairness property of Chan, and is probably only suitable when you have a small number of readers. We could make an MVar version with similar properties, but it wouldn't perform any better than TChan and wouldn't be composable, so this seems the best compromise:

  • Chan has fairness, single-wakeup (good for multiple readers)
  • TChan has isEmptyChan and unGetChan

comment:2 Changed 7 years ago by SamAnklesaria

Owner: set to SamAnklesaria

comment:3 Changed 7 years ago by SamAnklesaria

Owner: SamAnklesaria deleted

comment:4 Changed 7 years ago by simonmar

Resolution: fixed
Status: newclosed

Fixed by deprecating isEmptyChan and unGetChan (see above).

comment:5 Changed 6 years ago by mitar

Cc: mmitar@… added

The only case where I have been using isEmptyChan was in my version of non-blocking readChan, returning Maybe. Is it possible to define instead of isEmptyChan some non-blocking version of readChan with tryTakeMVar and tryPutMVar?

comment:6 Changed 5 years ago by singpolyma

I would also like a non-blocking readChan, and while tryTakeMVar seems like the right solution for that, from reading this report it seems that isEmptyChan will not cause a deadlock in this case, because no one is reading the Chan (unless you have multiple readers).

comment:7 Changed 2 weeks ago by osa1

It's been 7 years since isEmptyChan and unGetChan was deprecated (first release with deprecation seems to be 7.0). Should we delete them now?

comment:8 Changed 2 weeks ago by bgamari

Description: modified (diff)
Milestone: 7.0.18.4.1

Indeed, let's delete them for 8.4. I've opened #13561 to make sure we don't forget this.

comment:9 Changed 2 weeks ago by mitar

What about my proposal:

The only case where I have been using isEmptyChan was in my version of non-blocking readChan, returning Maybe. Is it possible to define instead of isEmptyChan some non-blocking version of readChan with tryTakeMVar and tryPutMVar?

comment:10 in reply to:  9 Changed 2 weeks ago by bgamari

Replying to mitar:

What about my proposal:

The only case where I have been using isEmptyChan was in my version of non-blocking readChan, returning Maybe. Is it possible to define instead of isEmptyChan some non-blocking version of readChan with tryTakeMVar and tryPutMVar?

Out of curiosity, why not move to STM if you need these sorts of operations?

I think the proposal is fine (assuming it's possible to implement safely; I am not familiar with the implementation of Chan). Do you want to put together a patch?

comment:11 Changed 2 weeks ago by mitar

Not sure if I am able to do so either. :-(

comment:12 Changed 2 weeks ago 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 takeMVars. Implementation of tryReadChan has to use tryTakeMVars, 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)

Note: See TracTickets for help on using tickets.