Concurrent execution might be a better place to start. :)

Obviously, this can be easily addressed in the interpreter. It is  
more of a problem for compiled code.

Garbage collectors (at least, concurrent ones) have a similar problem  
with tight loops. Inserting checks at each backward branch is the  
easiest solution, but carries significant overhead.

A more refined approach is to use self-modifying code to inject a  
call into the runtime: Stop the target thread, rewrite back-branches  
in the routine at the top of its stack (instead jumping into the  
runtime), flush the I-cache, and resume the target; the target will  
now break out of the loop within some reasonably bounded amount of  
time. The runtime obviously needs to then repair the routine before  
raising the exception. This approach requires significant code  
generator support and a bunch of tricky code in the runtime.

The former would probably be quite doable if you dig into the compiler.

On 2007-08-25, at 09:58, Daniel Bünzli wrote:

> Hello everybody,
>
> I would like to raise again the problem of portable thread  
> cancellation. The potential coming (?) of native dynamic linking  
> brings the stunning perspective of type-safe, native, plugins.  
> However to be able to use this in conjunction with user interfaces  
> (ui) or in a malicious environment it becomes even more acute to be  
> able to monitor/sandbox the execution of functions to avoid  
> application hangs.
>
> Thread cancellation allows to invoke an arbitrary function f on a  
> thread and stop its execution before completion, without  
> introducing checks for conditions in f -- rewriting every function  
> to do that goes against separation of concerns and malicious code  
> could just ignore such conditions.
>
> Xavier Leroy mentioned many time [1,2,3] that "Thread.kill" is not  
> an option. The argument is that this function is "unsafe" (not in  
> the typical sense) because the victim may be holding ressources and  
> it should be given the opportunity to release them before dying. As  
> such this function is not implemented in the native thread library  
> and will never be (btw. it is still not deprecated in 3.10). Other  
> solutions have been proposed [4,5]. [5] by Gerd Stolpmann is  
> portable. Note however that neither solution will work with  
> uncooperative threads, i.e. those that never perform any system  
> call or trigger the gc [7].
>
> In this [6] message Xavier Leroy acknowledges that having a  
> function "Thread.raise_in : exn -> Thread.t -> unit" to raise an  
> exception in the given thread is a reasonable alternative to  
> "Thread.kill". However the same message points out that this would  
> be difficult to implement for native threads that are blocked on  
> system calls and concludes :
>
> "So, the only easily implementable behavior is that the target  
> thread of a "raise_to" operation can delay the processing of the  
> exception until it returns from a system call.  But this behavior  
> is nearly useless..."
>
> While it wouldn't (or would it ?) solve the problem of  
> uncooperative threads and hence be useless in a malicious  
> environment, the "easy implementation" would be useful to monitor  
> cooperative computations in general -- well those that do not block  
> on system calls, but in a ui there may be many of these.
>
> I would appreciate having "Thread.raise_in" implemented, with the  
> system call caveat properly documented, instead of having to resort  
> to [5]. There is no feature request about this in the bug tracker.  
> Before filling a potentially useless one I would like to know what  
> you think about these problems and if there are things I have missed.
>
> Best,
>
> Daniel
>
> P.S. If your computations need to interact with the ui, forking is  
> out of question.
>
> [1] http://caml.inria.fr/pub/ml-archives/caml-list/ 
> 2000/05/4cf198c2f8dbf533cde462f2c65cf827.fr.html
> [2] http://caml.inria.fr/pub/ml-archives/caml-list/ 
> 2002/10/740fa6facb5981e6dc94c4b7d13ea7ed.fr.html
> [3] http://caml.inria.fr/pub/ml-archives/caml-list/ 
> 2003/05/8d9e6f406983d144111852cb7367ebc7.fr.html
> [4] http://caml.inria.fr/pub/ml-archives/caml-list/ 
> 2005/12/52715b2ecd818ac61af3ffb34e914ec1.fr.html
> [5] http://caml.inria.fr/pub/ml-archives/caml-list/ 
> 2005/11/71f680d0defd7ad890587f2b6d339ab5.fr.html
> [6] http://caml.inria.fr/pub/ml-archives/caml-list/ 
> 2002/09/36902268c9eb832e0042bf74426e14d2.fr.html
> [7] The difference between cooperative and uncooperative threads  
> can be seen by compiling the following two programs to _native_  
> code. The first one loops forever while the other doesn't (because  
> it allocates).
>
> --
> let () =
>   ignore (Thread.create (fun () -> while true do ignore (1 + 2)  
> done) ());
>   Thread.delay 1.
> --
> let () =
>   ignore (Thread.create (fun () -> while true do ignore (1. +. 2.)  
> done) ());
>   Thread.delay 1.
> --
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs



— Gordon