Race-condition in alternative 'System.Timeout.timeout' implementation

[Akio Takano]

I accidentally replied to Herbert privately. I'm forwarding the
message to the list.

- Takano Akio

---------- Forwarded message ----------
From: Akio Takano <tkn.akio at gmail.com>
Date: Mon, Feb 25, 2013 at 6:15 PM
Subject: Re: Race-condition in alternative 'System.Timeout.timeout'
implementation
To: Herbert Valerio Riedel <hvr at gnu.org>


Hi,

I think the problem is that E.unregisterTimeout doesn't guarantee that
no timeout will be delivered after it returns. This allows an
execution sequence like:

0. Thread A calls timeout2
1. Thread A registers a callback to the event manager
2. Thread A unregisters the callback
3. Thread A exits from the handleJust
4. The callback is triggered, killing thread A

If I understand correctly this can be worked around with an extra
mutex in timeout2. I'll attach my implementation. It's called timeout3
and is a bit slower than timeout2, but I haven't seen a leaking
exception with it.

On Mon, Feb 25, 2013 at 7:31 AM, Herbert Valerio Riedel <hvr at gnu.org> wrote:
> Hello *,
>
> I've been experimenting with an alternative implementation of
> 'System.Timeout.timeout'[1] which avoids the overhead of spawning a new
> thread for each invocation.
>
> Part of my motivation is to see if I can implement a faster version of
>
>     threadWaitReadTimeout :: Int -> Fd -> IO Bool
>     threadWaitReadTimeout to = liftM (maybe False (const True))
>                                . timeout to . threadWaitRead
>
> and thus exploit GHC's event notification system instead of having to
> reimplement a timeout-manager myself (like popular HTTP server libraries
> such as Snap or Warp do currently).
>
>
> The following Haskell program shows a proof-of-concept implementation
> derived directly from 'System.Timeout.timeout' together with a Criterion
> benchmark comparing the performance between the original and the
> alternative 'timeout' function wrapping a 'readMVar' call.
>
>
>
> On a i7-3770 with GHC-7.6.2/Linux/64bit ran with "+RTS -A4m -N4", the
> benchmark shows a 15x improvement for the new implementation (below 1
> uS) compared to the original implementation (~13 uS):
>
> ,----
> | benchmarking id
> | mean: 22.60933 ns, lb 22.50331 ns, ub 22.73515 ns, ci 0.950
> | std dev: 591.0383 ps, lb 509.6189 ps, ub 663.2670 ps, ci 0.950
> | found 17 outliers among 100 samples (17.0%)
> |   17 (17.0%) high mild
> | variance introduced by outliers: 19.992%
> | variance is moderately inflated by outliers
> |
> | benchmarking timeout_1ms
> | mean: 13.79584 us, lb 13.62939 us, ub 13.92814 us, ci 0.950
> | std dev: 756.3080 ns, lb 524.7628 ns, ub 1.068547 us, ci 0.950
> | found 14 outliers among 100 samples (14.0%)
> |   4 (4.0%) low severe
> |   5 (5.0%) high mild
> |   5 (5.0%) high severe
> | variance introduced by outliers: 52.484%
> | variance is severely inflated by outliers
> |
> | benchmarking timeout2_1ms
> | mean: 879.8152 ns, lb 874.5223 ns, ub 885.9759 ns, ci 0.950
> | std dev: 29.31963 ns, lb 25.65941 ns, ub 32.98116 ns, ci 0.950
> | found 9 outliers among 100 samples (9.0%)
> |   9 (9.0%) high mild
> | variance introduced by outliers: 28.734%
> | variance is moderately inflated by outliers
> | ...
> `----
>
> Alas there's a race-condition hidden somewhere I'm struggling with; When
> the timeout is set low enough, the internal 'Timeout2' exceptions leaks
> outside the 'timeout2' wrapper:
>
> ,----
> | ...
> | benchmarking timeout2_10us
> | newtimeout: <<timeout2>>
> `----
>
> I've tried rewriting the code but couldn't figure out a way to keep the
> exception from escaping 'timeout2'. Does the race-condition actually lie
> in the 'timeout2' implementation -- and if so, is it possible to rewrite
> 'timeout2' to solve it?
>
>
>  [1]: http://hackage.haskell.org/packages/archive/base/latest/doc/html/System-Timeout.html#v:timeout
>
> cheers,
>   hvr
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: timeout3.hs
Type: application/octet-stream
Size: 3330 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20130226/1ac1ca44/attachment.obj>