black hole detection and concurrency

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
27 messages Options
12
Reply | Threaded
Open this post in threaded view
|

black hole detection and concurrency

Conal Elliott
I'm looking for information about black hole detection with ghc.  I'm getting "<<loop>>" where I don't think there is an actual black hole.  I get this message sometimes with the unamb package, which is implemented with unsafePerformIO, concurrency, and killThread, as described in http://conal.net/blog/posts/functional-concurrency-with-unambiguous-choice/ and http://conal.net/blog/posts/smarter-termination-for-thread-racing/ .

Suppose I have a definition 'v = unsafePerformIO ...', and v is used more than once.   Evaluation (to whnf) of v is begun and the evaluation thread gets killed before evaluation is complete.  Then the second use begins.  Will the second evaluation be (incorrectly) flagged as a black hole?

I haven't found a simple, reproducible example of incorrect black-hole reporting.  My current examples are tied up with the Reactive library.  I do have another strange symptom, which is "thread killed" message.  I wonder if it's related to the <<loop>> message.  Code below.

    Thanks,  - Conal


import Prelude hiding (catch)
import System.IO.Unsafe
import Control.Concurrent
import Control.Exception


-- *** Exception: thread killed
main :: IO ()
main = print $ f (f True) where f v = (v `unamb` True) `seq` v

-- | Unambiguous choice operator.  Equivalent to the ambiguous choice
-- operator, but with arguments restricted to be equal where not bottom,
-- so that the choice doesn't matter.  See also 'amb'.
unamb :: a -> a -> a
unamb a b = unsafePerformIO (evaluate a `race` evaluate b)

-- | Race two actions against each other in separate threads, and pick
-- whichever finishes first.  See also 'amb'.
race :: IO a -> IO a -> IO a
race a b = do
    v <- newEmptyMVar
    let t x = x >>= putMVar v
    withThread (t a) $ withThread (t b) $ takeMVar v
 where
   withThread u v = bracket (forkIO u) killThread (const v)


_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: black hole detection and concurrency

sclv
I have a good theory on the latter symptom (the "thread killed"  
message). Sticking in some traces, as in my appended code, helped me  
to see what's going on. It seems to be exactly what you describe --  
the variable v is permanently bound to the exception it "evaluates"  
to.  Since the right hand True portion of the unamb evaluates more  
quickly, the spawned threads are killed and the left hand (the v)  
"evaluates" to "thread killed". This remains the value of its thunk  
when you access it later. This problem seems sort of innate to a pure  
unamb utilizing unsafePerformIO and asynchronous exceptions. A clever  
use of  `par` might conceivably help, given that if the par spark  
fails, the thunk can still be evaluated? Might be a dead end.

Here's the code:

go = f "f" (f "" True) where f s v = (unamb (s++"f") (s++"g") v True)  
`seq` v

--unamb :: String -> String -> a -> a -> a
unamb s s' a b = unsafePerformIO (race s s' (evaluate a) (evaluate b))

--race :: String -> String -> IO a -> IO a -> IO a
race s s' a b = do
     v <- newEmptyMVar
     let t x = x >>= putMVar v
     withThread s (t a) $ withThread s' (t b) $ takeMVar v
  where
    withThread s u v = bracket (forkIO u) (killNote s) (const $  
putStrLn ("in: " ++ s) >> v >>= \x -> putStrLn ("out: " ++ show x ++  
" "++ s) >> return x)

killNote s tid = throwTo tid (ErrorCall s)

And a GHCi session:

*Un> go
in: ff
in: fg
in: f
in: g
out: True fg
out: True ff
<interactive>: ff
*** Exception: ff

Cheers,
Sterl.

On Dec 26, 2008, at 1:15 AM, Conal Elliott wrote:

> I'm looking for information about black hole detection with ghc.  
> I'm getting "<<loop>>" where I don't think there is an actual black  
> hole.  I get this message sometimes with the unamb package, which  
> is implemented with unsafePerformIO, concurrency, and killThread,  
> as described in http://conal.net/blog/posts/functional-concurrency- 
> with-unambiguous-choice/ and http://conal.net/blog/posts/smarter- 
> termination-for-thread-racing/ .
>
> Suppose I have a definition 'v = unsafePerformIO ...', and v is  
> used more than once.   Evaluation (to whnf) of v is begun and the  
> evaluation thread gets killed before evaluation is complete.  Then  
> the second use begins.  Will the second evaluation be (incorrectly)  
> flagged as a black hole?
>
> I haven't found a simple, reproducible example of incorrect black-
> hole reporting.  My current examples are tied up with the Reactive  
> library.  I do have another strange symptom, which is "thread  
> killed" message.  I wonder if it's related to the <<loop>>  
> message.  Code below.
>
>     Thanks,  - Conal
>
>
> import Prelude hiding (catch)
> import System.IO.Unsafe
> import Control.Concurrent
> import Control.Exception
>
>
> -- *** Exception: thread killed
> main :: IO ()
> main = print $ f (f True) where f v = (v `unamb` True) `seq` v
>
> -- | Unambiguous choice operator.  Equivalent to the ambiguous choice
> -- operator, but with arguments restricted to be equal where not  
> bottom,
> -- so that the choice doesn't matter.  See also 'amb'.
> unamb :: a -> a -> a
> unamb a b = unsafePerformIO (evaluate a `race` evaluate b)
>
> -- | Race two actions against each other in separate threads, and pick
> -- whichever finishes first.  See also 'amb'.
> race :: IO a -> IO a -> IO a
> race a b = do
>     v <- newEmptyMVar
>     let t x = x >>= putMVar v
>     withThread (t a) $ withThread (t b) $ takeMVar v
>  where
>    withThread u v = bracket (forkIO u) killThread (const v)
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Fwd: black hole detection and concurrency

Conal Elliott
Thanks for the probing, Sterl.

I'm afraid I'm stuck here.  Without the more effective thread killing (in unamb), Reactive seems to be drowning in uselessly running threads.  With "improved" thread killing, I get many of these false black holes, instead of computed values.

I don't know whether this problem is solvable on top of ghc's current RTS, as you suggest (clever `par` use), but I don't know.  I'm out of my depth here and could sure use help.

Thanks,  - Conal

On Fri, Dec 26, 2008 at 6:09 PM, Sterling Clover <[hidden email]> wrote:
I have a good theory on the latter symptom (the "thread killed" message). Sticking in some traces, as in my appended code, helped me to see what's going on. It seems to be exactly what you describe -- the variable v is permanently bound to the exception it "evaluates" to.  Since the right hand True portion of the unamb evaluates more quickly, the spawned threads are killed and the left hand (the v) "evaluates" to "thread killed". This remains the value of its thunk when you access it later. This problem seems sort of innate to a pure unamb utilizing unsafePerformIO and asynchronous exceptions. A clever use of  `par` might conceivably help, given that if the par spark fails, the thunk can still be evaluated? Might be a dead end.

Here's the code:

go = f "f" (f "" True) where f s v = (unamb (s++"f") (s++"g") v True) `seq` v

--unamb :: String -> String -> a -> a -> a
unamb s s' a b = unsafePerformIO (race s s' (evaluate a) (evaluate b))

--race :: String -> String -> IO a -> IO a -> IO a
race s s' a b = do

   v <- newEmptyMVar
   let t x = x >>= putMVar v
   withThread s (t a) $ withThread s' (t b) $ takeMVar v
 where
  withThread s u v = bracket (forkIO u) (killNote s) (const $ putStrLn ("in: " ++ s) >> v >>= \x -> putStrLn ("out: " ++ show x ++ " "++ s) >> return x)

killNote s tid = throwTo tid (ErrorCall s)

And a GHCi session:

*Un> go
in: ff
in: fg
in: f
in: g
out: True fg
out: True ff
<interactive>: ff
*** Exception: ff

Cheers,
Sterl.


On Dec 26, 2008, at 1:15 AM, Conal Elliott wrote:

I'm looking for information about black hole detection with ghc.  I'm getting "<<loop>>" where I don't think there is an actual black hole.  I get this message sometimes with the unamb package, which is implemented with unsafePerformIO, concurrency, and killThread, as described in http://conal.net/blog/posts/functional-concurrency-with-unambiguous-choice/ and http://conal.net/blog/posts/smarter-termination-for-thread-racing/ .

Suppose I have a definition 'v = unsafePerformIO ...', and v is used more than once.   Evaluation (to whnf) of v is begun and the evaluation thread gets killed before evaluation is complete.  Then the second use begins.  Will the second evaluation be (incorrectly) flagged as a black hole?

I haven't found a simple, reproducible example of incorrect black-hole reporting.  My current examples are tied up with the Reactive library.  I do have another strange symptom, which is "thread killed" message.  I wonder if it's related to the <<loop>> message.  Code below.

   Thanks,  - Conal


import Prelude hiding (catch)
import System.IO.Unsafe
import Control.Concurrent
import Control.Exception


-- *** Exception: thread killed
main :: IO ()
main = print $ f (f True) where f v = (v `unamb` True) `seq` v

-- | Unambiguous choice operator.  Equivalent to the ambiguous choice
-- operator, but with arguments restricted to be equal where not bottom,
-- so that the choice doesn't matter.  See also 'amb'.
unamb :: a -> a -> a
unamb a b = unsafePerformIO (evaluate a `race` evaluate b)

-- | Race two actions against each other in separate threads, and pick
-- whichever finishes first.  See also 'amb'.
race :: IO a -> IO a -> IO a
race a b = do
   v <- newEmptyMVar
   let t x = x >>= putMVar v
   withThread (t a) $ withThread (t b) $ takeMVar v
 where
  withThread u v = bracket (forkIO u) killThread (const v)

_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users



_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: black hole detection and concurrency

Bertram Felgenhauer-2
In reply to this post by sclv
Sterling Clover wrote:
> I have a good theory on the latter symptom (the "thread killed" message).
> Sticking in some traces, as in my appended code, helped me to see what's
> going on. It seems to be exactly what you describe -- the variable v is
> permanently bound to the exception it "evaluates" to.  Since the right hand
> True portion of the unamb evaluates more quickly, the spawned threads are
> killed and the left hand (the v) "evaluates" to "thread killed". This
> remains the value of its thunk when you access it later.

Thank you for that analysis. It's intriguing. Here's a cut down example:

> import Control.Concurrent
> import Control.Concurrent.MVar
> import Control.Exception
> import System.IO.Unsafe
>
> main :: IO ()
> main = do
>     v <- newEmptyMVar
>     let y = print "a" >> takeMVar v >> print "b"
>         x = unsafePerformIO $ y `finally` return ()
>     tid <- forkIO $ evaluate x
>     yield
>     print "killing"
>     killThread tid
>     putMVar v ()
>     yield
>     print "finally"
>     print x

Output:
  "a"
  "killing"
  "finally"
  test: thread killed

Interestingly, the program works without the `finally` part, suspending
the IO action y in the middle:

Output without `finally`:
  "a"
  "killing"
  "finally"
  "b"
  ()

The `unamb` operator needs both behaviours: it has to kill its worker
threads if it turns out that its value is not yet needed, but it also
has to be suspended to allow it to be restarted later.

*after some digging in the ghc sources*

It may be possible to do the restarting manually:

>    let y = catchJust threadKilled
>                      (print "a" >> takeMVar v >> print "b")
>                      (\_ -> myThreadId >>= killThread >> y)
>        threadKilled ThreadKilled = Just ()
>        threadKilled _            = Nothing

(for ghc 6.8 use  threadKilled (AsyncException ThreadKilled) = Just ())

Output:
  "a"
  "killing"
  "finally"
  "a"
  "b"
  ()

The key part here is 'myThreadId >>= killThread' which throws an
asynchronous exception to the thread itself, causing the update
frames to be saved on the heap.

Note that 'myThreadId >>= killThread' is not equivalent to
'throw ThreadKilled'; it is a synchronous exception and replaces thunks
pointed to by the update frames by another call to the raise primitive -
the result being that the exception gets rethrown whenever such a thunk
is evaluated. This happens with 'finally' and 'bracket': they use
'throw' for re-throwing the exception.

See rts/RaiseAsync.c (raiseAsync() in particular) for the gory details
for the first case, and rts/Schedule.c, raiseExceptionHelper() for the
second case.

In the above code, there is a small window between catching the
ThreadKilled exception and throwing it again though, where other
exceptions may creep in. The only way I see of fixing that is to use
'block' and 'unblock' directly.

Here is an attempt at the 'race' function, using block, catch and
unblock. I'm not sure that it's correct. But it seems to work with
Sterling's example at least, which triggers a restart.

> race :: IO a -> IO a -> IO a
> race a b = block $ do
>     v <- newEmptyMVar
>     let t x = x >>= putMVar v
>     ta <- forkIO (t a)
>     tb <- forkIO (t b)
>     let cleanup = killThread ta >> killThread tb
>     unblock (do r <- takeMVar v; cleanup; return r)
>         `catch` \e -> case e of
>             ThreadKilled -> do
>                 cleanup
>                 myThreadId >>= killThread
>                 unblock (race a b)
>             e -> throwIO e

Bertram
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: black hole detection and concurrency

sclv

On Dec 27, 2008, at 9:02 AM, Bertram Felgenhauer wrote:

>
> The key part here is 'myThreadId >>= killThread' which throws an
> asynchronous exception to the thread itself, causing the update
> frames to be saved on the heap.
>
> Note that 'myThreadId >>= killThread' is not equivalent to
> 'throw ThreadKilled'; it is a synchronous exception and replaces  
> thunks
> pointed to by the update frames by another call to the raise  
> primitive -
> the result being that the exception gets rethrown whenever such a  
> thunk
> is evaluated. This happens with 'finally' and 'bracket': they use
> 'throw' for re-throwing the exception.
>
> See rts/RaiseAsync.c (raiseAsync() in particular) for the gory details
> for the first case, and rts/Schedule.c, raiseExceptionHelper() for the
> second case.
>
> In the above code, there is a small window between catching the
> ThreadKilled exception and throwing it again though, where other
> exceptions may creep in. The only way I see of fixing that is to use
> 'block' and 'unblock' directly.
>

That certainly seems to do the trick for the simple example at least.  
One way to reason about it better would be, instead of folding  
everything into the race function, to simply modify ghc's bracket  
function to give us the behavior we'd prefer (speaking of which, I  
recall there's something in the works for 6.12 or so to improve  
rethrowing of asynchronous exceptions?)

brackAsync before after thing =
   block (do
     a <- before
     r <- catch
            (unblock (thing a))
            (\_ -> after a >> myThreadId >>= killThread >> brackAsync  
before after thing )
     after a
     return r
  )
     where threadKilled ThreadKilled = Just ()
           threadKilled _            = Nothing

This brackAsync just drops in to the previous code where bracket was  
and appears to perform correctly. Further, if we place a trace after  
the killThread, we se it gets executed once when the example is read  
(i.e. a resumption) but it does not get executed if the (`seq` v) is  
removed from the example So this gives me some hope that this is  
actually doing what we'd like. I don't doubt it may have further  
kinks however.

Cheers,
Sterl.
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: black hole detection and concurrency

Bertram Felgenhauer-2
In reply to this post by Bertram Felgenhauer-2
Hi,

Bertram Felgenhauer wrote:
[snip]
> race :: IO a -> IO a -> IO a

Two quick notes on that function:

> race a b = block $ do
>     v <- newEmptyMVar
>     let t x = x >>= putMVar v

Should be
      let t x = unblock (x >>= putMVar v)

Otherwise the computation 'x' not be interruptible unless it explicitely
uses 'unblock' or a blocking operation like reading an MVar.

>     ta <- forkIO (t a)
>     tb <- forkIO (t b)
>     let cleanup = killThread ta >> killThread tb
>     unblock (do r <- takeMVar v; cleanup; return r)
>         `catch` \e -> case e of
>             ThreadKilled -> do
>                 cleanup
>                 myThreadId >>= killThread
>                 unblock (race a b)

On the other hand, this 'unblock' should have no effect: If we ever
return here, it'll be in a different thread, or after another exception
handler has enabled exceptions for the current thread.

>             e -> throwIO e

Oops. This should call cleanup as well. (I guess it should be done
before the 'case' expression)

              e -> cleanup >> throwIO e

Bertram
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: black hole detection and concurrency

Bertram Felgenhauer-2
In reply to this post by sclv
Sterling Clover wrote:

> On Dec 27, 2008, at 9:02 AM, Bertram Felgenhauer wrote:
>> In the above code, there is a small window between catching the
>> ThreadKilled exception and throwing it again though, where other
>> exceptions may creep in. The only way I see of fixing that is to use
>> 'block' and 'unblock' directly.
>
> That certainly seems to do the trick for the simple example at least. One
> way to reason about it better would be, instead of folding everything into
> the race function, to simply modify ghc's bracket function to give us the
> behavior we'd prefer (speaking of which, I recall there's something in the
> works for 6.12 or so to improve rethrowing of asynchronous exceptions?)
>
> brackAsync before after thing =
>   block (do
>     a <- before
>     r <- catch
>            (unblock (thing a))
>            (\_ -> after a >> myThreadId >>= killThread >>
>                   brackAsync before after thing )
>     after a
>     return r
>  )
>     where threadKilled ThreadKilled = Just ()
>           threadKilled _            = Nothing

This code turns any exception into ThreadKilled further down the stack.

  (\e -> do
       after a
       myThreadId >>= flip throwTo (e :: SomeException)
       ...

might do the trick.

My assumption was that anything but 'ThreadKilled' would be a
real error. This isn't really true, I guess - thanks to throwTo,
any exception could be asynchronous.

If an exception is thrown, 'after a' is run again after the computation
has resumed.

That's why I did the cleanup within the 'catch'.

But there's no reason why you couldn't do that as well:

  brackAsync before after thing =
    block $ do
      a <- before
      catch  (unblock (thing a) >>= \r -> after a >> return r) $
             \e -> do
                    after a
                    myThreadId >>= flip throwTo (e :: SomeException)
                    brackAsync before after thing )

> This brackAsync just drops in to the previous code where bracket was and
> appears to perform correctly.

Right. 'race' should also unblock exceptions in the worker threads,

    withThread u v = brackAsync (forkIO (unblock u)) killThread (const v)

but that's an independent change.

> Further, if we place a trace after the
> killThread, we se it gets executed once when the example is read (i.e. a
> resumption) but it does not get executed if the (`seq` v) is removed from
> the example So this gives me some hope that this is actually doing what
> we'd like. I don't doubt it may have further kinks however.

At least the GHC RTS has support for the hard part - unwinding the stack
so that computations can be resumed seamlessly.

I'm not sure which of the approaches I like better - it seems that we
have a choice between turning async exceptions into sync ones or vice
versa, and neither choice is strictly superior to the other.

Enjoy,

Bertram

'race' update:
- Bugfix: Previously, only AsyncException-s would be caught.
  Use 'fromException' to select the ThreadKilled exception.
- I tried using a custom 'SuspendException' type, but this resulted in
  'test: SuspendException' messages on the console, while ThreadKilled
  is silently ignored... as documented:
     http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent.html#v%3AforkIO
     (http://tinyurl.com/9t5pxs)
- Tweak: Block exceptions while running 'cleanup' to avoid killing
  threads twice.
- Trick: takeMVar is a blocking operation, so exceptions can be
  delivered while it's waiting - there's no need to use 'unblock' for
  this. In other words,  unblock (takeMVar v)  and  takeMVar v  are
  essentially equivalent for our purposes.

race :: IO a -> IO a -> IO a
race a b = block $ do
    v <- newEmptyMVar
    let t x = unblock (x >>= putMVar v)
    ta <- forkIO (t a)
    tb <- forkIO (t b)
    let cleanup = killThread ta >> killThread tb
    (do r <- takeMVar v; cleanup; return r) `catch`
        \e -> cleanup >>
            case fromException e of
                Just ThreadKilled -> do
                    myThreadId >>= killThread
                    unblock (race a b)
                _ -> throwIO e
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: [reactive] Re: black hole detection and concurrency

Conal Elliott
This is a neat trick indeed!  I'd appreciate an explanation of killing one's own thread and then continuing (with a restart in this case).  How does the post-kill resumption occur?  That is, how does control pass to the tail-recursive call after the self-kill?

  - Conal


2008/12/28 Peter Verswyvelen <[hidden email]>
I fail to understand this part of the code:

           case fromException e of
               Just ThreadKilled -> do
                   myThreadId >>= killThread
                   unblock (race a b)

So the current thread gets killed synchronously, then then the race function is evaluated again? The latter I don't get.



On Sun, Dec 28, 2008 at 3:03 AM, Bertram Felgenhauer <[hidden email]> wrote:
Sterling Clover wrote:
> On Dec 27, 2008, at 9:02 AM, Bertram Felgenhauer wrote:
>> In the above code, there is a small window between catching the
>> ThreadKilled exception and throwing it again though, where other
>> exceptions may creep in. The only way I see of fixing that is to use
>> 'block' and 'unblock' directly.
>
> That certainly seems to do the trick for the simple example at least. One
> way to reason about it better would be, instead of folding everything into
> the race function, to simply modify ghc's bracket function to give us the
> behavior we'd prefer (speaking of which, I recall there's something in the
> works for 6.12 or so to improve rethrowing of asynchronous exceptions?)
>
> brackAsync before after thing =
>   block (do
>     a <- before
>     r <- catch
>            (unblock (thing a))
>            (\_ -> after a >> myThreadId >>= killThread >>
>                   brackAsync before after thing )
>     after a
>     return r
>  )
>     where threadKilled ThreadKilled = Just ()
>           threadKilled _            = Nothing

This code turns any exception into ThreadKilled further down the stack.

 (\e -> do
      after a
      myThreadId >>= flip throwTo (e :: SomeException)
      ...

might do the trick.

My assumption was that anything but 'ThreadKilled' would be a
real error. This isn't really true, I guess - thanks to throwTo,
any exception could be asynchronous.

If an exception is thrown, 'after a' is run again after the computation
has resumed.

That's why I did the cleanup within the 'catch'.

But there's no reason why you couldn't do that as well:

 brackAsync before after thing =
   block $ do
     a <- before
     catch  (unblock (thing a) >>= \r -> after a >> return r) $
            \e -> do
                   after a
                   myThreadId >>= flip throwTo (e :: SomeException)
                   brackAsync before after thing )

> This brackAsync just drops in to the previous code where bracket was and
> appears to perform correctly.

Right. 'race' should also unblock exceptions in the worker threads,

   withThread u v = brackAsync (forkIO (unblock u)) killThread (const v)

but that's an independent change.

> Further, if we place a trace after the
> killThread, we se it gets executed once when the example is read (i.e. a
> resumption) but it does not get executed if the (`seq` v) is removed from
> the example So this gives me some hope that this is actually doing what
> we'd like. I don't doubt it may have further kinks however.

At least the GHC RTS has support for the hard part - unwinding the stack
so that computations can be resumed seamlessly.

I'm not sure which of the approaches I like better - it seems that we
have a choice between turning async exceptions into sync ones or vice
versa, and neither choice is strictly superior to the other.

Enjoy,

Bertram

'race' update:
- Bugfix: Previously, only AsyncException-s would be caught.
 Use 'fromException' to select the ThreadKilled exception.
- I tried using a custom 'SuspendException' type, but this resulted in
 'test: SuspendException' messages on the console, while ThreadKilled
 is silently ignored... as documented:
    http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent.html#v%3AforkIO
    (http://tinyurl.com/9t5pxs)
- Tweak: Block exceptions while running 'cleanup' to avoid killing
 threads twice.
- Trick: takeMVar is a blocking operation, so exceptions can be
 delivered while it's waiting - there's no need to use 'unblock' for
 this. In other words,  unblock (takeMVar v)  and  takeMVar v  are
 essentially equivalent for our purposes.

race :: IO a -> IO a -> IO a
race a b = block $ do
   v <- newEmptyMVar
   let t x = unblock (x >>= putMVar v)
   ta <- forkIO (t a)
   tb <- forkIO (t b)
   let cleanup = killThread ta >> killThread tb
   (do r <- takeMVar v; cleanup; return r) `catch`
       \e -> cleanup >>
           case fromException e of
               Just ThreadKilled -> do
                   myThreadId >>= killThread
                   unblock (race a b)
               _ -> throwIO e
_______________________________________________
Reactive mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/reactive


_______________________________________________
Reactive mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/reactive



_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: [reactive] Re: black hole detection and concurrency

Conal Elliott
In reply to this post by Bertram Felgenhauer-2
Thanks very much for these ideas.  Peter Verswyvelen suggested running the example repeatedly to see if it always runs correctly.  He found, and I verified, that the example runs fine with Bertram's last version of unamb below, unless it's compiled with -threaded and run with +RTS -N2.  In the latter case, it locks up after a while.

I also tried a version with brackAsync and found that it eventually locks up even under ghci.  When compiled & run multi-threaded, it locks up almost immediately.

I've attached a module, TestRace.hs, containing these experiments.

    - Conal

On Sat, Dec 27, 2008 at 6:03 PM, Bertram Felgenhauer <[hidden email]> wrote:
Sterling Clover wrote:
> On Dec 27, 2008, at 9:02 AM, Bertram Felgenhauer wrote:
>> In the above code, there is a small window between catching the
>> ThreadKilled exception and throwing it again though, where other
>> exceptions may creep in. The only way I see of fixing that is to use
>> 'block' and 'unblock' directly.
>
> That certainly seems to do the trick for the simple example at least. One
> way to reason about it better would be, instead of folding everything into
> the race function, to simply modify ghc's bracket function to give us the
> behavior we'd prefer (speaking of which, I recall there's something in the
> works for 6.12 or so to improve rethrowing of asynchronous exceptions?)
>
> brackAsync before after thing =
>   block (do
>     a <- before
>     r <- catch
>            (unblock (thing a))
>            (\_ -> after a >> myThreadId >>= killThread >>
>                   brackAsync before after thing )
>     after a
>     return r
>  )
>     where threadKilled ThreadKilled = Just ()
>           threadKilled _            = Nothing

This code turns any exception into ThreadKilled further down the stack.

 (\e -> do
      after a
      myThreadId >>= flip throwTo (e :: SomeException)
      ...

might do the trick.

My assumption was that anything but 'ThreadKilled' would be a
real error. This isn't really true, I guess - thanks to throwTo,
any exception could be asynchronous.

If an exception is thrown, 'after a' is run again after the computation
has resumed.

That's why I did the cleanup within the 'catch'.

But there's no reason why you couldn't do that as well:

 brackAsync before after thing =
   block $ do
     a <- before
     catch  (unblock (thing a) >>= \r -> after a >> return r) $
            \e -> do
                   after a
                   myThreadId >>= flip throwTo (e :: SomeException)
                   brackAsync before after thing )

> This brackAsync just drops in to the previous code where bracket was and
> appears to perform correctly.

Right. 'race' should also unblock exceptions in the worker threads,

   withThread u v = brackAsync (forkIO (unblock u)) killThread (const v)

but that's an independent change.

> Further, if we place a trace after the
> killThread, we se it gets executed once when the example is read (i.e. a
> resumption) but it does not get executed if the (`seq` v) is removed from
> the example So this gives me some hope that this is actually doing what
> we'd like. I don't doubt it may have further kinks however.

At least the GHC RTS has support for the hard part - unwinding the stack
so that computations can be resumed seamlessly.

I'm not sure which of the approaches I like better - it seems that we
have a choice between turning async exceptions into sync ones or vice
versa, and neither choice is strictly superior to the other.

Enjoy,

Bertram

'race' update:
- Bugfix: Previously, only AsyncException-s would be caught.
 Use 'fromException' to select the ThreadKilled exception.
- I tried using a custom 'SuspendException' type, but this resulted in
 'test: SuspendException' messages on the console, while ThreadKilled
 is silently ignored... as documented:
    http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent.html#v%3AforkIO
    (http://tinyurl.com/9t5pxs)
- Tweak: Block exceptions while running 'cleanup' to avoid killing
 threads twice.
- Trick: takeMVar is a blocking operation, so exceptions can be
 delivered while it's waiting - there's no need to use 'unblock' for
 this. In other words,  unblock (takeMVar v)  and  takeMVar v  are
 essentially equivalent for our purposes.

race :: IO a -> IO a -> IO a
race a b = block $ do
   v <- newEmptyMVar
   let t x = unblock (x >>= putMVar v)
   ta <- forkIO (t a)
   tb <- forkIO (t b)
   let cleanup = killThread ta >> killThread tb
   (do r <- takeMVar v; cleanup; return r) `catch`
       \e -> cleanup >>
           case fromException e of
               Just ThreadKilled -> do
                   myThreadId >>= killThread
                   unblock (race a b)
               _ -> throwIO e
_______________________________________________
Reactive mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/reactive


_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

TestRace.hs (4K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [reactive] Re: black hole detection and concurrency

Bertram Felgenhauer-2
In reply to this post by Bertram Felgenhauer-2
Peter Verswyvelen wrote:
> I fail to understand this part of the code:
>            case fromException e of
>                Just ThreadKilled -> do
>                    myThreadId >>= killThread
>                    unblock (race a b)
>
> So the current thread gets killed synchronously, then then the race function
> is evaluated again? The latter I don't get.

Let's look at what happens when an asynchronous exception arrives.

The current thread gets killed. It gets killed asynchronously; as far
as the RTS knows, the exceptionit might happen inside a pure computation
which may be accessible to other threads. This means that the RTS has to
patch things up so that reentering the corresponding thunks continues
the computation - because another thread might need the value later. It
does that by traversing the stack and turning update frames into ap
nodes on the heap, and linking the entered thunks to those using an
indirection (again, see RaiseAsync.c for details).

Now in fact, IO actions are indistinguishable from pure computations by
the RTS, so this mechanism also makes IO actions resumable, in
principle, if you can access the corresponding thunk somehow. Normally
you can't - there is no reference to that thunk - but unsafePerformIO
gives you that reference.

So in the above example, the current thread gets killed. However, the IO
action (suspended right before the 'unblock (race a b)') is still
accessible through the unsafePerformIO thunk. When another thread enters
that thunk, execution resumes at that point. It may also be the same
thread if it caught the exception further down the stack and later
enters the unsafePerformIO thunk again.

I don't understand all the interactions here - I don't know why the code
is racy in the parallel RTS.

Bertram
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

RE: black hole detection and concurrency

Simon Peyton Jones
In reply to this post by Conal Elliott

I have not followed the details of this thread, but Simon Marlow will be back in action on 5 Jan and he should know.

 

What I do know is that this is supposed to happen:

·         If a *synchronous* exception S is raised when evaluating a thunk, the thunk is permanently updated to “throw S”.

·         If an *asynchronous* exception A is raised when evaluating  a thunk, the stack is copied into the heap, and the thunk is updated with a new thunk that, when evaluated, will resume evaluation where it left off.

 

But there may be some funny interactions with unsafePerformIO. 

 

Simon

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of Conal Elliott
Sent: 26 December 2008 06:15
To: [hidden email]
Subject: black hole detection and concurrency

 

I'm looking for information about black hole detection with ghc.  I'm getting "<<loop>>" where I don't think there is an actual black hole.  I get this message sometimes with the unamb package, which is implemented with unsafePerformIO, concurrency, and killThread, as described in http://conal.net/blog/posts/functional-concurrency-with-unambiguous-choice/ and http://conal.net/blog/posts/smarter-termination-for-thread-racing/ .

Suppose I have a definition 'v = unsafePerformIO ...', and v is used more than once.   Evaluation (to whnf) of v is begun and the evaluation thread gets killed before evaluation is complete.  Then the second use begins.  Will the second evaluation be (incorrectly) flagged as a black hole?

I haven't found a simple, reproducible example of incorrect black-hole reporting.  My current examples are tied up with the Reactive library.  I do have another strange symptom, which is "thread killed" message.  I wonder if it's related to the <<loop>> message.  Code below.

    Thanks,  - Conal


import Prelude hiding (catch)
import System.IO.Unsafe
import Control.Concurrent
import Control.Exception


-- *** Exception: thread killed
main :: IO ()
main = print $ f (f True) where f v = (v `unamb` True) `seq` v

-- | Unambiguous choice operator.  Equivalent to the ambiguous choice
-- operator, but with arguments restricted to be equal where not bottom,
-- so that the choice doesn't matter.  See also 'amb'.
unamb :: a -> a -> a
unamb a b = unsafePerformIO (evaluate a `race` evaluate b)

-- | Race two actions against each other in separate threads, and pick
-- whichever finishes first.  See also 'amb'.
race :: IO a -> IO a -> IO a
race a b = do
    v <- newEmptyMVar
    let t x = x >>= putMVar v
    withThread (t a) $ withThread (t b) $ takeMVar v
 where
   withThread u v = bracket (forkIO u) killThread (const v)


_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

RE: black hole detection and concurrency

Simon Peyton Jones
In reply to this post by sclv
| I have a good theory on the latter symptom (the "thread killed"
| message). Sticking in some traces, as in my appended code, helped me
| to see what's going on. It seems to be exactly what you describe --
| the variable v is permanently bound to the exception it "evaluates"
| to.  Since the right hand True portion of the unamb evaluates more
| quickly, the spawned threads are killed and the left hand (the v)
| "evaluates" to "thread killed".

This is odd (to me).  The "permanently bound" stuff applies only to *synchronous* exceptions, which thread-killing is not.  Simon M will have more to say when he gets back

Simon
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: black hole detection and concurrency

Bertram Felgenhauer-2
Simon Peyton-Jones wrote:

> | I have a good theory on the latter symptom (the "thread killed"
> | message). Sticking in some traces, as in my appended code, helped me
> | to see what's going on. It seems to be exactly what you describe --
> | the variable v is permanently bound to the exception it "evaluates"
> | to.  Since the right hand True portion of the unamb evaluates more
> | quickly, the spawned threads are killed and the left hand (the v)
> | "evaluates" to "thread killed".
>
> This is odd (to me).  The "permanently bound" stuff applies only to
> *synchronous* exceptions, which thread-killing is not.  Simon M will
> have more to say when he gets back

This is true when the exception is raised the first time. However, some
exception handling functions like 'bracket' catch the exception, do
their cleanup, and then throw the exception again. This is done in
onException, and goes through throwIO and eventually raiseIO#. At this
point the originally asynchronous exception has become a synchronous
one.

As I wrote elsewhere in this thread, this should not be a problem
without unsafePerformIO.

Bertram
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: [reactive] Re: black hole detection and concurrency

Isaac Dupree
In reply to this post by Bertram Felgenhauer-2
Bertram Felgenhauer wrote:
> Now in fact, IO actions are indistinguishable from pure computations by
> the RTS, so this mechanism also makes IO actions resumable, in
> principle, if you can access the corresponding thunk somehow. Normally
> you can't - there is no reference to that thunk - but unsafePerformIO
> gives you that reference.

I wonder if other things break in the presence of resumable
IO computations... the first thing that comes to mind is,
inside a "block" or "unblock" (which have to initiate, take
down and deal with all that infrastructure -- luckily you
only use them inside a separate thread, a forkIO within the
unsafePerformIO... Which admittedly makes things horribly
confusing in its own way. Also does forkIO copy any state?
it copies blocked status now, which the unamb-calling thread
might have...).  The state of the thread when entering the
computation again, could be different than it was when the
computation was first suspended, I'm guessing.  (At least
you need to be careful about what invariants you assume; I'm
not yet sure if it's possible to be careful enough.)

-Isaac
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: [reactive] Re: black hole detection and concurrency

Bertram Felgenhauer-2
In reply to this post by Conal Elliott
Conal Elliott wrote:
> Thanks very much for these ideas.  Peter Verswyvelen suggested running the
> example repeatedly to see if it always runs correctly.  He found, and I
> verified, that the example runs fine with Bertram's last version of unamb
> below, *unless* it's compiled with -threaded and run with +RTS -N2.  In the
> latter case, it locks up after a while.

It seems that we've found an RTS bug. If a thread is started with
exceptions blocked, then throwTo might never deliver its exception and
block forever, as can be seen with the following test program, which
locks up after a while (immediately with the non-threaded RTS)

  import Control.Exception
  import Control.Concurrent
  import Control.Monad
 
  test n = do
      t <- block $ forkIO yield
      yield
      putStr $ show n ++ ": kill\n"
      killThread t
 
  main = forM_ [1..] test

Or, even more convincing:

  import Control.Exception
  import GHC.Conc
 
  main = do
      t1 <- block $ forkIO yield
      t2 <- forkIO $ killThread t1
      yield
      yield
      threadStatus t1 >>= print
      threadStatus t2 >>= print

prints (fairly reliably, it seems):

  ThreadFinished
  ThreadBlocked BlockedOnException

(Trac is giving me errors right now. I'm planning to report this later.)

> I also tried a version with brackAsync and found that it eventually locks up
> even under ghci.  When compiled & run multi-threaded, it locks up almost
> immediately.

> -- This one locks up after a while even in ghci.  When compiled -threaded
> -- and run +RTS -N2, it locks up almost immediately.
> a `race` b = do
>    v <- newEmptyMVar
>    let t x = x >>= putMVar v
>    withThread (t a) $ withThread (t b) $ takeMVar v
>  where
>   withThread u v = brackAsync (forkIO u) killThread (const v)

At the point the 'forkIO' is run, exceptions are blocked, making the
thread basically immortal. Using

>   withThread u v = brackAsync (forkIO $ unblock u) killThread (const v)

we get the same behaviour as with my 'race' - it works for a while, but
locks up eventually.

I believe that the actual lockup is similar to the test programs above
in all cases - what's different is just the probability of triggering
it.

regards,

Bertram
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: [reactive] Re: black hole detection and concurrency

Conal Elliott
Indeed -- many thanks to Bertram, Sterling, Peter & others for the help!  I think getting this bug fixed will solve Reactive's mysterious bugs and unblock its progress.

    - Conal

On Sat, Jan 3, 2009 at 1:20 PM, Peter Verswyvelen <[hidden email]> wrote:
That is very good news! Let's hope it's a bug that is easy enough to
fix, since I guess the RTS is very tricky.

Thanks for all this effort. It would explain a lot of strange behaviour.

Cheers,
Peter Verswyvelen
CTO - Anygma.com


On Sat, Jan 3, 2009 at 4:48 PM, Bertram Felgenhauer
<[hidden email]> wrote:
> Conal Elliott wrote:
>> Thanks very much for these ideas.  Peter Verswyvelen suggested running the
>> example repeatedly to see if it always runs correctly.  He found, and I
>> verified, that the example runs fine with Bertram's last version of unamb
>> below, *unless* it's compiled with -threaded and run with +RTS -N2.  In the
>> latter case, it locks up after a while.
>
> It seems that we've found an RTS bug. If a thread is started with
> exceptions blocked, then throwTo might never deliver its exception and
> block forever, as can be seen with the following test program, which
> locks up after a while (immediately with the non-threaded RTS)
>
>  import Control.Exception
>  import Control.Concurrent
>  import Control.Monad
>
>  test n = do
>      t <- block $ forkIO yield
>      yield
>      putStr $ show n ++ ": kill\n"
>      killThread t
>
>  main = forM_ [1..] test
>
> Or, even more convincing:
>
>  import Control.Exception
>  import GHC.Conc
>
>  main = do
>      t1 <- block $ forkIO yield
>      t2 <- forkIO $ killThread t1
>      yield
>      yield
>      threadStatus t1 >>= print
>      threadStatus t2 >>= print
>
> prints (fairly reliably, it seems):
>
>  ThreadFinished
>  ThreadBlocked BlockedOnException
>
> (Trac is giving me errors right now. I'm planning to report this later.)
>
>> I also tried a version with brackAsync and found that it eventually locks up
>> even under ghci.  When compiled & run multi-threaded, it locks up almost
>> immediately.
>
>> -- This one locks up after a while even in ghci.  When compiled -threaded
>> -- and run +RTS -N2, it locks up almost immediately.
>> a `race` b = do
>>    v <- newEmptyMVar
>>    let t x = x >>= putMVar v
>>    withThread (t a) $ withThread (t b) $ takeMVar v
>>  where
>>   withThread u v = brackAsync (forkIO u) killThread (const v)
>
> At the point the 'forkIO' is run, exceptions are blocked, making the
> thread basically immortal. Using
>
>>   withThread u v = brackAsync (forkIO $ unblock u) killThread (const v)
>
> we get the same behaviour as with my 'race' - it works for a while, but
> locks up eventually.
>
> I believe that the actual lockup is similar to the test programs above
> in all cases - what's different is just the probability of triggering
> it.
>
> regards,
>
> Bertram
> _______________________________________________
> Reactive mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/reactive
>
_______________________________________________
Reactive mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/reactive


_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: [reactive] Re: black hole detection and concurrency

Isaac Dupree-3
In reply to this post by Bertram Felgenhauer-2
therefore mapException is equally buggy!

> mapException :: (Exception e1, Exception e2) => (e1 -> e2) -> a -> a
> mapException f v = unsafePerformIO (catch (evaluate v)
>                                           (\x -> throw (f x)))

If it maps an asynchronous exception.. and it's re-thrown as
synchronous... the same non-resumability happens!
mapException is a particular culprit because of the
unsafePerformIO (so you had a good reason to expect
resumability, since it's for a pure computation, not in IO)

- does anyone use mapException?

- is there some reason that we don't have all "throw"s
(synch. or asynch.) "patch up" the thunks?  (memory leaks or
serious inefficiency or something?)

if "yes", I don't think mapException can currently be
implemented; we'd need some way in its "catch" to detect
whether the thrown exception was asynchronous, and *iff* so,
throw the new exception asynchronously (if synchronous,
rethrow synchronously).  Or some equivalent.  Or maybe some
add some magic to unsafePerformIO (probably a bad idea).

-Isaac
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: [reactive] Re: black hole detection and concurrency

Lauri Alanko
On Sun, Jan 04, 2009 at 07:40:38PM -0500, Isaac Dupree wrote:
> - does anyone use mapException?

I was the one who originally requested it, since it was mentioned in
the paper and looked reasonable, but was missing from GHC. My
motivation was that it could be used by a pure function to hide the
exception behavior of an auxiliary function that it used internally.
I can't really claim to have used it very much, though.


Lauri
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

RE: [reactive] Re: black hole detection and concurrency

Sittampalam, Ganesh
 
> On Sun, Jan 04, 2009 at 07:40:38PM -0500, Isaac Dupree wrote:
> > - does anyone use mapException?

> I was the one who originally requested it, since it was mentioned
> in the paper and looked reasonable, but was missing from GHC.
> My motivation was that it could be used by a pure function to
> hide the exception behavior of an auxiliary function that it used
> internally. I can't really claim to have used it very much, though.

I use it sometimes to provide a pseudo "call-stack" for errors.

Ganesh

==============================================================================
Please access the attached hyperlink for an important electronic communications disclaimer:

http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html
==============================================================================

_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|

Re: black hole detection and concurrency

Ian Lynagh
In reply to this post by Bertram Felgenhauer-2
On Mon, Dec 29, 2008 at 05:07:22PM +0100, Bertram Felgenhauer wrote:

> Simon Peyton-Jones wrote:
> >
> > This is odd (to me).  The "permanently bound" stuff applies only to
> > *synchronous* exceptions, which thread-killing is not.  Simon M will
> > have more to say when he gets back
>
> This is true when the exception is raised the first time. However, some
> exception handling functions like 'bracket' catch the exception, do
> their cleanup, and then throw the exception again. This is done in
> onException, and goes through throwIO and eventually raiseIO#. At this
> point the originally asynchronous exception has become a synchronous
> one.

We don't currently have a way to know whether an exception was thrown
asynchronously or not, right?

Should we actually be throwing
    data SomeExceptionSync = SomeExceptionSync Bool -- synchronous?
                                               SomeException
with catch etc ignoring the Bool, but bracket etc handling it
appropriately?


Thanks
Ian

_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
12