Opened 6 years ago

Closed 6 years ago

#7493 closed bug (fixed)

STM and TVar report incorrect results

Reported by: parcs Owned by:
Priority: highest Milestone: 7.6.2
Component: Runtime System Version: 7.6.1
Keywords: Cc: v.dijk.bas@…, felipe.lessa@…
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

On Haskell Cafe, I posted:

I'm getting strange behavior when using the 'many' combinator to read zero or more items off of a TQueue with readTQueue. The script that exhibits this behavior is as follows:

import Control.Concurrent.STM
import Control.Concurrent
import Control.Monad
import Control.Applicative

main = do
    q <- newTQueueIO
    atomically $ writeTQueue q True
    atomically $ writeTQueue q False
    forever $ do
        xs <- atomically $ many $ readTQueue q
        print xs
        threadDelay 500000

I'd expect the output of the script to be:

[True,False]
[]
[]
...

However, that is not the case: the actual output of the script is:

[True,False]
[True,False]
[True,False]
...

If 1 element (say, True) is written into the TQueue instead of 2, then the output of the script is:

[True]
[]
[]
...

Which is expected behavior, but inconsistent with the behavior when the TQueue has 2 or more elements in it.

Is this considered a bug, or undocumented behavior of TQueue?


Bas vas Dijk noted that this may be a bug in STM, and provided a condensed test case which reproduces the behavior of my original script:

$ cat stmTest.hs
import Control.Concurrent.STM
main = do
  x <- atomically $ do
         t <- newTVar 1
         writeTVar t 2
         ((readTVar t >> retry) `orElse` return ()) `orElse` return ()
         readTVar t
  print x

$ ghc --make stmTest.hs -fforce-recomp -threaded -o stmTest && ./stmTest
[1 of 1] Compiling Main             ( stmTest.hs, stmTest.o )
Linking stmTest ...
1

The program prints 1 when it should print 2.

Change History (11)

comment:1 Changed 6 years ago by meteficha

Cc: felipe.lessa@… added

comment:2 Changed 6 years ago by simonmar

difficulty: Unknown
Milestone: 7.6.2
Priority: normalhighest
Status: newmerge

Fixed (sorry, I didn't notice that you'd filed a ticket until just now):

commit f184d9caffa09750ef6a374a7987b9213d6db28e

Author: Simon Marlow <marlowsd@gmail.com>
Date:   Mon Dec 10 12:00:54 2012 +0000

    Fix a bug in the handling of nested orElse
    
    Exposed by the following snippet, courtesy of Bas van Dijk and Patrick
    Palka on libraries@haskell.org:
    
    import Control.Concurrent.STM
    main = do
      x <- atomically $ do
             t <- newTVar 1
             writeTVar t 2
             ((readTVar t >> retry) `orElse` return ()) `orElse` return ()
             readTVar t
      print x

comment:3 Changed 6 years ago by igloo

Resolution: fixed
Status: mergeclosed

comment:4 Changed 6 years ago by fryguybob

I built with the fix and for the first program I'm getting:

[True,False]
[False]
[]
[]
...

comment:5 Changed 6 years ago by parcs

Resolution: fixed
Status: closednew

I am getting the same output as fryguybob using GHC 7.7 20121214 and STM 2.4.2.

comment:6 Changed 6 years ago by fryguybob

I've reduced the first program to the following:

import Control.Concurrent.STM

main = do
  x <- atomically $ do
         r <- newTVar []
         writeTVar r [2]
         writeTVar r [] `orElse` return ()
         readTVar r
  print x

This outputs [2] when I would expect []. If I use Ints it does not fail and if I have different values for each of the write or new's it works:

import Control.Concurrent.STM

main = do
  x <- atomically $ do
         r <- newTVar [1]
         writeTVar r [2]
         writeTVar r [1] `orElse` return ()
         readTVar r
  print x

Outputs: [1]

import Control.Concurrent.STM

main = do
  x <- atomically $ do
         r <- newTVar 1
         writeTVar r 2
         writeTVar r 1 `orElse` return ()
         readTVar r
  print x

Output: 1

Also interesting:

import Control.Concurrent.STM

main = do
  x <- atomically $ do
         r <- newTVar Nothing
         writeTVar r (Just 2)
         writeTVar r Nothing `orElse` return ()
         readTVar r
  print x

Output: Just 2

I'll start digging around to see what is going on with this example.

comment:7 Changed 6 years ago by fryguybob

I've traced down the point of divergence between a test that works and one that does not. The following works:

import Control.Concurrent.STM

main = do
  x <- atomically $ do
         r <- newTVar 1
         writeTVar r 2
         writeTVar r 1 `orElse` return ()
         readTVar r
  print x

But if we change to:

import Control.Concurrent.STM

main = do
  x <- atomically $ do
         let a = 1
         r <- newTVar a
         writeTVar r 2
         writeTVar r a `orElse` return ()
         readTVar r
  print x

Then when we try to commit the inner transaction with stmCommitNestedTransaction we enter validate_and_acquire_ownership and hit entry_is_update (code here) which returns false (the current value is the exact a that initialized in newTVar). In the one that works each 1 is a different thunk (Integer, unlike Int I said before; using Int it does indeed fail).

I'm still tracking down what happens after this, but now we know the difference between the examples.

comment:8 Changed 6 years ago by fryguybob

It looks like this particular case is not accounted for. If an outer transaction writes the inner transaction needs to compare with that value to know if it is an update, not with the originally read value (which we need for knowing if there was an update from outside). Worse yet, the write we need to see could be several levels out. Perhaps it would be better to fix it on the other side of things. If a write doesn't update, then when we merge_read_into if the outer record entry is an update, then we know the inner has reversed the update. But here we can't distinguish a write to match the expected value and a read (which we would not want to take as an indication that we should revert our outer update).

Perhaps another approach could be to look when we do an stmWriteTVar to see if we are an inner transaction writing what matches the expected value. If so, built a thunk (indirection?) so we are sure to get a new value that will be seen by the outer transaction.

comment:9 Changed 6 years ago by marlowsd@…

commit a006ecdfd381fa75ab16ddb66c3a2b247f359eb8

Author: Simon Marlow <marlowsd@gmail.com>
Date:   Tue Dec 18 09:10:26 2012 +0000

    A better fix for #7493 (see comment for details)

 rts/STM.c |   64 +++++++++++++++++++++++++++++++++++++++++-------------------
 1 files changed, 44 insertions(+), 20 deletions(-)

comment:10 Changed 6 years ago by simonmar

Status: newmerge

I reverted the previous fix:

commit 55c55f141b8b312512cce1d7e0fbd3a8088de964

Author: Simon Marlow <marlowsd@gmail.com>
Date:   Tue Dec 18 08:43:29 2012 +0000

    Revert "Fix a bug in the handling of nested orElse"
    
    This reverts commit f184d9caffa09750ef6a374a7987b9213d6db28e.
    
    The next commit will fix it in a better way.

please merge both commits.

@fryguybob, @parcs: see if you can break it again!

comment:11 Changed 6 years ago by igloo

Resolution: fixed
Status: mergeclosed
Note: See TracTickets for help on using tickets.