From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.1 required=5.0 tests=AWL,HTML_MESSAGE autolearn=disabled version=3.1.3 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 4D7ABBC69 for ; Sat, 25 Aug 2007 17:57:29 +0200 (CEST) Received: from smtpout.mac.com (smtpout.mac.com [17.250.248.186]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l7PFvRHD005913 for ; Sat, 25 Aug 2007 17:57:28 +0200 Received: from mac.com (smtpin03-en2 [10.13.10.148]) by smtpout.mac.com (Xserve/smtpout16/MantshX 4.0) with ESMTP id l7PFvP6Y015697 for ; Sat, 25 Aug 2007 08:57:25 -0700 (PDT) Received: from [192.168.8.152] (c-24-218-151-219.hsd1.ma.comcast.net [24.218.151.219]) (authenticated bits=0) by mac.com (Xserve/smtpin03/MantshX 4.0) with ESMTP id l7PFvMM3020133 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NO) for ; Sat, 25 Aug 2007 08:57:23 -0700 (PDT) Mime-Version: 1.0 (Apple Message framework v752.3) In-Reply-To: <9FA25C33-04DD-46BD-8959-873DDD2FFF82@epfl.ch> References: <9FA25C33-04DD-46BD-8959-873DDD2FFF82@epfl.ch> Content-Type: multipart/alternative; boundary=Apple-Mail-1--703169176 Message-Id: <02547442-C79D-4F5B-B6DF-37623033DA2B@mac.com> From: Gordon Henriksen Subject: Re: [Caml-list] Has the thread cancellation problem evolved ? Date: Sat, 25 Aug 2007 11:57:08 -0400 To: caml-list@yquem.inria.fr X-Mailer: Apple Mail (2.752.3) X-j-chkmail-Score: MSGID : 46D05167.004 on concorde : j-chkmail score : X : 0/20 1 0.000 -> 1 X-Miltered: at concorde with ID 46D05167.004 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; inserting:01 runtime:01 runtime:01 bounded:01 doable:01 compiler:01 bunzli:01 type-safe:01 sandbox:01 rewriting:01 gerd:01 stolpmann:01 exn:01 computations:01 bug:01 --Apple-Mail-1--703169176 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=WINDOWS-1252; delsp=yes; format=flowed Concurrent execution might be a better place to start. :) Obviously, this can be easily addressed in the interpreter. It is =20 more of a problem for compiled code. Garbage collectors (at least, concurrent ones) have a similar problem =20= with tight loops. Inserting checks at each backward branch is the =20 easiest solution, but carries significant overhead. A more refined approach is to use self-modifying code to inject a =20 call into the runtime: Stop the target thread, rewrite back-branches =20 in the routine at the top of its stack (instead jumping into the =20 runtime), flush the I-cache, and resume the target; the target will =20 now break out of the loop within some reasonably bounded amount of =20 time. The runtime obviously needs to then repair the routine before =20 raising the exception. This approach requires significant code =20 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=FCnzli wrote: > Hello everybody, > > I would like to raise again the problem of portable thread =20 > cancellation. The potential coming (?) of native dynamic linking =20 > brings the stunning perspective of type-safe, native, plugins. =20 > However to be able to use this in conjunction with user interfaces =20 > (ui) or in a malicious environment it becomes even more acute to be =20= > able to monitor/sandbox the execution of functions to avoid =20 > application hangs. > > Thread cancellation allows to invoke an arbitrary function f on a =20 > thread and stop its execution before completion, without =20 > introducing checks for conditions in f -- rewriting every function =20 > to do that goes against separation of concerns and malicious code =20 > could just ignore such conditions. > > Xavier Leroy mentioned many time [1,2,3] that "Thread.kill" is not =20 > an option. The argument is that this function is "unsafe" (not in =20 > the typical sense) because the victim may be holding ressources and =20= > it should be given the opportunity to release them before dying. As =20= > such this function is not implemented in the native thread library =20 > and will never be (btw. it is still not deprecated in 3.10). Other =20 > solutions have been proposed [4,5]. [5] by Gerd Stolpmann is =20 > portable. Note however that neither solution will work with =20 > uncooperative threads, i.e. those that never perform any system =20 > call or trigger the gc [7]. > > In this [6] message Xavier Leroy acknowledges that having a =20 > function "Thread.raise_in : exn -> Thread.t -> unit" to raise an =20 > exception in the given thread is a reasonable alternative to =20 > "Thread.kill". However the same message points out that this would =20 > be difficult to implement for native threads that are blocked on =20 > system calls and concludes : > > "So, the only easily implementable behavior is that the target =20 > thread of a "raise_to" operation can delay the processing of the =20 > exception until it returns from a system call. But this behavior =20 > is nearly useless..." > > While it wouldn't (or would it ?) solve the problem of =20 > uncooperative threads and hence be useless in a malicious =20 > environment, the "easy implementation" would be useful to monitor =20 > cooperative computations in general -- well those that do not block =20= > on system calls, but in a ui there may be many of these. > > I would appreciate having "Thread.raise_in" implemented, with the =20 > system call caveat properly documented, instead of having to resort =20= > to [5]. There is no feature request about this in the bug tracker. =20 > Before filling a potentially useless one I would like to know what =20 > 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 =20 > out of question. > > [1] http://caml.inria.fr/pub/ml-archives/caml-list/=20 > 2000/05/4cf198c2f8dbf533cde462f2c65cf827.fr.html > [2] http://caml.inria.fr/pub/ml-archives/caml-list/=20 > 2002/10/740fa6facb5981e6dc94c4b7d13ea7ed.fr.html > [3] http://caml.inria.fr/pub/ml-archives/caml-list/=20 > 2003/05/8d9e6f406983d144111852cb7367ebc7.fr.html > [4] http://caml.inria.fr/pub/ml-archives/caml-list/=20 > 2005/12/52715b2ecd818ac61af3ffb34e914ec1.fr.html > [5] http://caml.inria.fr/pub/ml-archives/caml-list/=20 > 2005/11/71f680d0defd7ad890587f2b6d339ab5.fr.html > [6] http://caml.inria.fr/pub/ml-archives/caml-list/=20 > 2002/09/36902268c9eb832e0042bf74426e14d2.fr.html > [7] The difference between cooperative and uncooperative threads =20 > can be seen by compiling the following two programs to _native_ =20 > code. The first one loops forever while the other doesn't (because =20 > it allocates). > > -- > let () =3D > ignore (Thread.create (fun () -> while true do ignore (1 + 2) =20 > done) ()); > Thread.delay 1. > -- > let () =3D > ignore (Thread.create (fun () -> while true do ignore (1. +. 2.) =20 > 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 =97 Gordon --Apple-Mail-1--703169176 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=WINDOWS-1252
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=A0routine 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=FCnzli 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.=A0 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.


Daniel

P.S. If your computations need = to interact with the ui, forking is out of question.

[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 () = =3D
=A0 ignore (Thread.create (fun () = -> while true do ignore (1 + 2) done) ());
=A0 = Thread.delay 1.
--
let () =3D
=A0 ignore (Thread.create (fun () = -> while true do ignore (1. +. 2.) done) ());
=A0 = Thread.delay 1.
--

Caml-list mailing list. Subscription = management:



=97 Gordon

= --Apple-Mail-1--703169176--