Has the thread cancellation problem evolved ?

Has the thread cancellation problem evolved ?

[Daniel Bünzli]

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.
--

Re: [Caml-list] Has the thread cancellation problem evolved ?

[skaller]

On Sat, 2007-08-25 at 15:58 +0200, Daniel Bünzli wrote:
> Hello everybody,
> 
> I would like to raise again the problem of portable thread  
> cancellation.

There is something I don't understand here.

Thread cancellation is a function of the native operating
system. You mention

> Thread cancellation allows to invoke an arbitrary function f on a  
> thread and stop its execution before completion,

and no operating system I know supports that. Posix, for example
allows cancelling a thread ONLY at specified system calls,
typically blocking socket related ones. It also misses one
critical one (I forget which).

The only other way to cancel a thread on Posix is to send a 
signal and AFAIK there is no standardised signal to do that
(only for processes?)

So you're asking Xavier to implement something impossible.
It can't be done in native code in the first place, forget
about safely. Futhermore:

> [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].

And it is almost certainly not portable. Portable means on ALL
operating systems .. including Windows.

> 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.

The general solution to this problem is to kill the whole process.
This ensures resources are cleaned up at the OS level, if not
the user level.

BTW: you can say "this isn't feasible for a web server" and I can
reply "No, and neither is destroying a thread out of the thread pool".

Otherwise, somewhere somehow there has to be a check done: whether
it is by the OS, by the Ocaml gc, or some user function.

Throwing an Ocaml exception is a very bad idea as a response!
It isn't just that resources won't be cleaned up .. it could
happen in the middle of C code interfacing Ocaml, and leave
the whole process in an inconsistent state (if the gc method
was used).

The bottom line is: there is necessarily NO safe way to clean
up a rogue thread, and if a thread does go rogue, the whole
process should be condemned.

If the source of the problem is a blocking operation, the solution
is simple: don't use blocking operations!

Otherwise, if your client thread is "cooperative" then checking
a cancellation flag at judicious points is tedious, but the best
solution.

What you REALLY want here is a Monadic combinator to automate
the checking .. :)

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

It isn't out of the question, but is very nasty ;(


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Daniel Bünzli]

Le 25 août 07 à 17:29, skaller a écrit :

> There is something I don't understand here.

What you don't understand is that ocaml has a runtime system which  
leaves some room for designing around what exists at the os level.

> If the source of the problem is a blocking operation, the solution
> is simple: don't use blocking operations!

This is not the source of the problem. What I want is to allow users  
to initiate and cancel computations whenever they want. Computations  
can be lengthy even tough they do not invoke a blocking operation.

The problem is that libraries are not -- and should not -- be  
designed with cancellation in mind, say every function has an  
optional parameter that allows to stop the computation. Cancellation  
should be a service of the runtime system, and denying its usefulness  
because it could be misused makes no sense, I can also open a file  
and never close it, it is a matter of programming discipline.

Daniel

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Till Varoquaux]

Hmm,

I have a very partial answer. I had to implement timeouts on blocking
calls recently I had to resort to alarms. You seem to be well
documented so I don't think this will be new to you. It might however
be useful to less seasoned hackers.

Here is the sample code:

exception Timeout
let timeout timeout f arg=
 let resChan=Event.new_channel () in
 let res=Event.receive resChan in
 let _= Thread.create begin
  fun () ->
   Unix.alarm timeout;
   Sys.signal Sys.sigalrm (Sys.Signal_handle begin
                            fun _ ->
                             Event.sync(Event.send resChan None);
                             Thread.exit ()
                           end);
   let computation=Event.send resChan (Some (f arg)) in
   Event.sync(computation)
 end ()
 in
 match Event.sync(res) with
  | Some e -> e
  | None -> raise Timeout

let _ =
 let r=timeout 1 (fun a -> Thread.delay 1.5; a) "arg" in
 print_string r


As a side note I thinks Threads.raise_in would be awesome, it might be
hard to add in the language though...

Till
On 8/27/07, Daniel Bünzli <daniel.buenzli@epfl.ch> wrote:
>
> Le 25 août 07 à 17:29, skaller a écrit :
>
> > There is something I don't understand here.
>
> What you don't understand is that ocaml has a runtime system which
> leaves some room for designing around what exists at the os level.
>
> > If the source of the problem is a blocking operation, the solution
> > is simple: don't use blocking operations!
>
> This is not the source of the problem. What I want is to allow users
> to initiate and cancel computations whenever they want. Computations
> can be lengthy even tough they do not invoke a blocking operation.
>
> The problem is that libraries are not -- and should not -- be
> designed with cancellation in mind, say every function has an
> optional parameter that allows to stop the computation. Cancellation
> should be a service of the runtime system, and denying its usefulness
> because it could be misused makes no sense, I can also open a file
> and never close it, it is a matter of programming discipline.
>
> Daniel
>
> _______________________________________________
> 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
>

Re: [Caml-list] Has the thread cancellation problem evolved ?

[skaller]

On Mon, 2007-08-27 at 01:47 +0200, Daniel Bünzli wrote:
> Le 25 août 07 à 17:29, skaller a écrit :
> 
> > There is something I don't understand here.
> 
> What you don't understand is that ocaml has a runtime system which  
> leaves some room for designing around what exists at the os level.

I do understand that, but it doesn't make any difference
to the fact that if you're running OS threads you need to use
OS facilities to support things like cancellation.

Also I at least would not like to see some extra feature dependent
on the current uniprocessor model, so hooking, say, the gc,
or the global lock, may be a bad idea because in a future multiprocessor
execution model those things may not be present.

> > If the source of the problem is a blocking operation, the solution
> > is simple: don't use blocking operations!
> 
> This is not the source of the problem. What I want is to allow users  
> to initiate and cancel computations whenever they want.

That is a reasonable crude idea, but not precise because you haven't
specified what 'should' happen to any acquired resources which would
normally be released under program control.

>  Computations  
> can be lengthy even tough they do not invoke a blocking operation.

Agree.

> The problem is that libraries are not -- and should not -- be  
> designed with cancellation in mind, say every function has an  
> optional parameter that allows to stop the computation.

I cannot agree with that claim at this time. If a library
acquires resources and should support cancellation, then the library
must also make provision for relinquishing those resources,
including on cancellation.

It is a fact, that in C++ libraries have to be designed to handle
unexpected *synchronous* exceptions.. they even have a term for it:
'exception safe', and it has a heavy influence on library design.

So the actual evidence is that you're not correct: libraries DO
have to be designed to allow for abnormal termination.

Synchronous exception handling is part of Ocaml. Asynchronous
exception handling is not. So whilst with synchronous exceptions
you can expect the program to catch and deal with the exceptions
because they're thrown by the users code in the first place,
or at least a library documenting that this may happen,
being able to handle async exceptions is likely to be an impediment
to programming in a way that manages resources safely.

I do know something about this -- I am responsible for an official
National Body "veto" on the C++ Standard on this issue. 
(Exception safe coding support) Note that is just ordinary
exception handling, particularly in a polymorphic context
where you can't know what exceptions will be thrown.. we're
still talking about synchronous exceptions.

I have no doubt async exceptions will also influence
library design.

>  Cancellation  
> should be a service of the runtime system, and denying its usefulness  
> because it could be misused makes no sense, I can also open a file  
> and never close it, it is a matter of programming discipline.

I'm not denying usefulness, I believe I simply claimed it couldn't
be implemented.

The problem here is roughly that OS support automatic release
of many resources held by a process, when the process is killed.
But there is no corresponding support for threads.

This issue arises EVEN for cancellation of Posix threads at
defined cancellation points. C executes 'on exit' procedures.
For C++ the issue has been a matter for years of study by
subgroups of the ISO Standardisation committee. Also those
responsible for system ABI's actually HAD to specify some kind
of behaviour, including the answer to the question: what happens
if an exception hits the bottom of a thread stack?

Note that the issue is nontrivial. For example if you DO execute
code after cancellation .. what happens on if there is a subsequent
cancellation? What happens if the cancellation code blocks?

I guess my point is: you're asking something difficult, even
for OS design, and reflecting it in Ocaml is going to be even
more problematic.

To make progress here you might instead consider a hybrid solution.
For example, Ocaml provide ability set a hook into the garbage
collector. That may be a bad idea, I don't know. Perhaps with a hook
you can complete a solution for certain kinds of application on 
certain OS, without imposing the responsibility for a complete
solution on Inria.


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Daniel Bünzli]

Le 27 août 07 à 06:38, skaller a écrit :

> That is a reasonable crude idea, but not precise because you haven't
> specified what 'should' happen to any acquired resources which would
> normally be released under program control.

They are left as is. If the programmer didn't care to handle, this is  
his problem, as when he forgets to close a file. The problem is if  
you don't even give the opportunity to the programmer to handle the  
problem, this is why Thread.kill is bad but Thread.raise_in acceptable.

> I cannot agree with that claim at this time. If a library
> acquires resources and should support cancellation, then the library
> must also make provision for relinquishing those resources,
> including on cancellation.

I think that in gc'd environment this problem is less acute. How many  
of the libraries out there are using locks or do fd business I don't  
know _under_ the module interface ? Any library that does not perform  
that kind of thing, and to overapproximate that does not bind to C,  
won't have a problem with cancellation. If their resource usage is  
explicit then I'm writing the resources allocation and deallocation  
and my thread will release them in the exception handler that I will  
write. I'll design and care for it.

Daniel

Re: [Caml-list] Has the thread cancellation problem evolved ?

[skaller]

On Mon, 2007-08-27 at 12:12 +0200, Daniel Bünzli wrote:
> Le 27 août 07 à 06:38, skaller a écrit :
> 
> > That is a reasonable crude idea, but not precise because you haven't
> > specified what 'should' happen to any acquired resources which would
> > normally be released under program control.
> 
> They are left as is. If the programmer didn't care to handle, this is  
> his problem, as when he forgets to close a file. The problem is if  
> you don't even give the opportunity to the programmer to handle the  
> problem, this is why Thread.kill is bad but Thread.raise_in acceptable.

I agree with you rationale, but it isn't clear the conclusion follows
that raise_in is acceptable.

To give a simple pseudo code:

	begin
		let f = open_out filename in
		write f stuff;
		close f
	end

which would work assuming write doesn't raise, will fail to
work in the presence of async exceptions. This roughly means
every resource acquisition MUST be guarded by a try/with
which catches the async exception and releases the resource
before re-raising it.

With a simple stack protocol this is fine .. but we use the
heap and garbage collectors because the stack isn't enough,
so presumably this protocol could be hard to follow.

In C++, RAIII is used for this, i.e. object whose constructors
acquire a resource and destructors release it, together with
say ref counted pointers, so that throwing an exception unwinds
all the objects, i.e. executes the destructors to release the
resources.

Ocaml has no such facility. SO before even considering raise_in
you need to propose one: possibly this would involve a monadic
programming style, but I don't really know.

I would guess, adding async exceptions, plus a requirement
to properly manage resources, could have a radical impact
on acceptable library designs.

Please note this is a guess. I don't know. But I think before
even asking for async exception, you'd need at least one
proposal to handle them.

> > I cannot agree with that claim at this time. If a library
> > acquires resources and should support cancellation, then the library
> > must also make provision for relinquishing those resources,
> > including on cancellation.
> 
> I think that in gc'd environment this problem is less acute. 

That may be so, on the assumption calls to the gc are frequent,
which sounds fairly reasonable to me.

> How many  
> of the libraries out there are using locks or do fd business I don't  
> know _under_ the module interface ? Any library that does not perform  
> that kind of thing, and to overapproximate that does not bind to C,  
> won't have a problem with cancellation. If their resource usage is  
> explicit then I'm writing the resources allocation and deallocation  
> and my thread will release them in the exception handler that I will  
> write. I'll design and care for it.

It is not so simple I suspect .. you can put an exception handler
at the start of the thread, but then how do you know what resources
to release?

If there is a registry of them .. all the routine allocating resources
must use the registry.

The problem is try/raise/with is a stack protocol: you cannot wrap
allocations in it, if the allocation returns the resource.

I'm not saying there is no solution.. but if you have libraries,
particularly ones with HOFs, then you have to actually have a
standardised protocol that all the libraries have to follow.


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Jon Harrop]

On Monday 27 August 2007 12:28:39 skaller wrote:
> In C++, RAIII is used for this, i.e. object whose constructors
> acquire a resource and destructors release it, together with
> say ref counted pointers, so that throwing an exception unwinds
> all the objects, i.e. executes the destructors to release the
> resources.
>
> Ocaml has no such facility...

Sounds like you want an OCaml equivalent of .NET's Dispose. That's very easy 
to achieve in OCaml but it is rarely useful.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Daniel Bünzli]

Le 27 août 07 à 13:28, skaller a écrit :

> I agree with you rationale, but it isn't clear the conclusion follows
> that raise_in is acceptable.
>
> To give a simple pseudo code:
>
> 	begin
> 		let f = open_out filename in
> 		write f stuff;
> 		close f
> 	end
>
> which would work assuming write doesn't raise, will fail to
> work in the presence of async exceptions.

It won't fail to work, there is the possibility that f will never be  
closed, that's it. The point is that the code written above should  
not be written in a library (library IO routines should always take a  
channel or a stream, not a filename, for other reasons aswell, e.g.  
to IO on a socket). Such code should be written by the user of the  
library, and if he knows he needs to handle cancellation he will act  
accordingly. Note that you don't catch Sys_error here...

> This roughly means
> every resource acquisition MUST be guarded by a try/with
> which catches the async exception and releases the resource
> before re-raising it.

Yes but if you are not a sloppy programmer you already guard your  
operations on channels to handle the various errors that can occur  
and End_of_file. And if you are really not a sloppy programmer you  
already have and use your own version of try/finally :

let apply f x ~finally y =
   let res = try f x with exn -> finally y; raise exn in
   finally y;
   res

Anyway most of the things I would like to cancel are not functions  
dealing with channels or locks but functions that do perform  
intensive numerical computations. In the presence of a human user you  
cannot let the ui hang for arbitrary long period of time, he should  
be able to cancel if he gets bored.

Daniel

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Jon Harrop]

On Monday 27 August 2007 13:24:34 Daniel Bünzli wrote:
> And if you are really not a sloppy programmer you
> already have and use your own version of try/finally :
>
> let apply f x ~finally y =
>    let res = try f x with exn -> finally y; raise exn in
>    finally y;
>    res

Ironically, that's broken. :-)

If your handler "finally" raises an exception then it would replace the Abort 
exception. You should ignore any exception raised by "finally" if "f" raises 
an exception.

> Anyway most of the things I would like to cancel are not functions
> dealing with channels or locks but functions that do perform
> intensive numerical computations. In the presence of a human user you
> cannot let the ui hang for arbitrary long period of time, he should
> be able to cancel if he gets bored.

Then write in CPS and weave an abortable continuation between each step.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Daniel Bünzli]

Le 27 août 07 à 14:38, Jon Harrop a écrit :

> On Monday 27 August 2007 13:24:34 Daniel Bünzli wrote:
>> And if you are really not a sloppy programmer you
>> already have and use your own version of try/finally :
>>
>> let apply f x ~finally y =
>>    let res = try f x with exn -> finally y; raise exn in
>>    finally y;
>>    res
>
> Ironically, that's broken. :-)
>
> If your handler "finally" raises an exception then it would replace  
> the Abort
> exception. You should ignore any exception raised by "finally" if  
> "f" raises
> an exception.

It depends on which exception you eventually want to get at the  
toplevel, it is a choice. But I agree your choice makes more sense  
than mine.

> Then write in CPS and weave an abortable continuation between each  
> step.

Why not, but this a very low level solution and I cannot reuse  
existing libraries that are not written in this style. I don't think  
it is a reasonable answer.

Daniel

Re: [Caml-list] Has the thread cancellation problem evolved ?

[skaller]

On Mon, 2007-08-27 at 13:38 +0100, Jon Harrop wrote:
> In the presence of a human user you
> > cannot let the ui hang for arbitrary long period of time, he should
> > be able to cancel if he gets bored.
> 
> Then write in CPS and weave an abortable continuation between each step.

But there's no assurance that will work: Felix uses a closely related
technique involving resumptions, but the compiler also optimises
almost every one of those 'steps' away.

Encoding regular checks is too hard; in that Daniel is right
the user shouldn't have to bother. However a compromise might be:
in most code, block async exceptions, at specified points,
do a check. In computationally intensive code not allocating resources, 
allow them anywhere and guard with a single trap.

Well .. this reminds me of the problem of scheduling parallel
processing .. skeletons and Ocaml3p come to mind here.

It seems in this model type system support is required: ideally
the 'guarded intensive calculation' would be a monad?

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Markus E L]

Daniel Bünzli wrote:

> Le 25 août 07 à 17:29, skaller a écrit :
>
>> There is something I don't understand here.
>
> What you don't understand is that ocaml has a runtime system which
> leaves some room for designing around what exists at the os level.
>
>> If the source of the problem is a blocking operation, the solution
>> is simple: don't use blocking operations!
>
> This is not the source of the problem. What I want is to allow users
> to initiate and cancel computations whenever they want. Computations
> can be lengthy even tough they do not invoke a blocking operation.

I'm sure the approach I'm suggesting might be too simple, perhaps you
even have thought about it and it doesn't meet your demands: But have
you thought about doing the users computation in a fork()ed child
process and communicate the result(s) back by marshalling over a pipe?
The communication band width after forking is limited (but the child
process has all the data of the parent process at the time of the
fork()). On the other side it would solve the (a) code unloading
problem and (b) the cancellation every time problem (you can always
cancel by sending as SIGKILL :-).

Regards -- Markus

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Gerd Stolpmann]

Am Sonntag, den 26.08.2007, 01:29 +1000 schrieb skaller:
> > [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].
> 
> And it is almost certainly not portable. Portable means on ALL
> operating systems .. including Windows.

Just reading again what I suggested two years ago. This suggestion is
implementable on Windows, as the O'Caml runtime has its own mechanisms
to check for asynchronous events (it is needed for switching between
threads).

Nevertheless, I don't think this is a good thing. Raising an exception
at potentially any moment is a problematic thing. E.g. code like

let x = try Some(List.assoc ... with _) -> None

where the author implicitly assumes that it is only Not_found that can
happen and the code is just plain wrong if anything else is encoded into
the exception.

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Daniel Bünzli]

Le 28 août 07 à 01:33, Gerd Stolpmann a écrit :

> Nevertheless, I don't think this is a good thing. Raising an exception
> at potentially any moment is a problematic thing. E.g. code like
>
> let x = try Some(List.assoc ... with _) -> None
>
> where the author implicitly assumes that it is only Not_found that can
> happen and the code is just plain wrong if anything else is encoded  
> into
> the exception.

But this is sloppy programming anyway. The author is plain wrong in  
assuming that only Not_found can be raised, he is asking for a  
potential time consuming debugging session.

1) If x is polymorphic then List.assoc may raise Invalid_argument  
(because of compare).

2) If the computation of x is embedded in a larger computation the  
call to List.assoc may raise Stack_overflow.

3) The allocation of the block for Some may raise Out_of_memory.

4) If we are in the toplevel Sys.Break may be raised.

IMHO the only place where a catch all handler is allowed is in a  
toplevel main loop (or a function monitoring other computations).

Daniel

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Gerd Stolpmann]

Am Dienstag, den 28.08.2007, 11:26 +0200 schrieb Daniel Bünzli:
> Le 28 août 07 à 01:33, Gerd Stolpmann a écrit :
> 
> > Nevertheless, I don't think this is a good thing. Raising an exception
> > at potentially any moment is a problematic thing. E.g. code like
> >
> > let x = try Some(List.assoc ... with _) -> None
> >
> > where the author implicitly assumes that it is only Not_found that can
> > happen and the code is just plain wrong if anything else is encoded  
> > into
> > the exception.
> 
> But this is sloppy programming anyway. The author is plain wrong in  
> assuming that only Not_found can be raised, he is asking for a  
> potential time consuming debugging session.
> 
> 1) If x is polymorphic then List.assoc may raise Invalid_argument  
> (because of compare).
> 
> 2) If the computation of x is embedded in a larger computation the  
> call to List.assoc may raise Stack_overflow.
> 
> 3) The allocation of the block for Some may raise Out_of_memory.
> 
> 4) If we are in the toplevel Sys.Break may be raised.
> 
> IMHO the only place where a catch all handler is allowed is in a  
> toplevel main loop (or a function monitoring other computations).

Of course, my example is a bit simplistic. My point is that it is anyway
difficult to get exception handling right in larger programs, and that
overloading this mechanism with another feature is questionable. We have
generally two kinds of exceptions: programmatic use to pass unusual
result values back, or to exit some recursion (like Not_found), and
those for runtime conditions/limitations (like Out_of_memory) (and some
exceptions are in between). Handling the second type is difficult, as
the program is probably already in a weird state when you try to handle
the condition.

Stopping threads is simple as long as if you only think of computations:
yes, you can stop any computation by raising an exception. But I don't
see a good way to stop I/O operations. Simply close all file
descriptors? Yes, possible, but you may leave files in an unrecoverable
state. It can even have very unwanted effects. Imagine you release locks
at this moment - this may trigger other processes doing something.

I see your problem, but there is no general solution. A thread of
execution is always part of a larger system, and you cannot stop a
system by stopping a thread. The word "stop" has simply no meaning in
this larger context.

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Phone: +49-6151-153855                  Fax: +49-6151-997714
------------------------------------------------------------

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Daniel Bünzli]

Le 28 août 07 à 13:42, Gerd Stolpmann a écrit :

> But I don't see a good way to stop I/O operations. Simply close all  
> file
> descriptors? Yes, possible, but you may leave files in an  
> unrecoverable
> state.

Again I'm not interested in stopping IO but I just note that if the  
user gets bored because its app hangs on IO, he will kill the process  
and the effect on files will be the same.

I still think -- despite the caveats one needs to be aware of, e.g.  
about IO -- the feature is worthwhile and essential for ui programs  
that can trigger expensive computations. But since it seems to be  
seen more as a curse than a blessing I think I'll forget about the  
wish and try to get around with Gerd's hack.

Thanks for the discussion,

Daniel

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Gordon Henriksen]

On Aug 28, 2007, at 05:26, Daniel Bünzli wrote:

> Le 28 août 07 à 01:33, Gerd Stolpmann a écrit :
>
>> Nevertheless, I don't think this is a good thing. Raising an  
>> exception at potentially any moment is a problematic thing. E.g.  
>> code like
>>
>> let x = try Some(List.assoc ... with _) -> None
>>
>> where the author implicitly assumes that it is only Not_found that  
>> can happen and the code is just plain wrong if anything else is  
>> encoded into the exception.
>
> But this is sloppy programming anyway. The author is plain wrong in  
> assuming that only Not_found can be raised, he is asking for a  
> potential time consuming debugging session.

Such problems are too common to ignore. .NET defuses them by treating  
ThreadAbortException specially.

“When a call is made to the Abort method to destroy a thread, the  
common language runtime throws a ThreadAbortException.  
ThreadAbortException is a special exception that can be caught, but  
it will automatically be raised again at the end of the catch block.  
When this exception is raised, the runtime executes all the finally  
blocks before ending the thread. Since the thread can do an unbounded  
computation in the finally blocks, or call Thread.ResetAbort to  
cancel the abort, there is no guarantee that the thread will ever end.”

http://msdn2.microsoft.com/en-us/library/ 
system.threading.threadabortexception.aspx

— Gordon

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Brian Hurt]

Gordon Henriksen wrote:

>
> Such problems are too common to ignore. .NET defuses them by treating  
> ThreadAbortException specially.
>
> “When a call is made to the Abort method to destroy a thread, the  
> common language runtime throws a ThreadAbortException.  
> ThreadAbortException is a special exception that can be caught, but  
> it will automatically be raised again at the end of the catch block.  
> When this exception is raised, the runtime executes all the finally  
> blocks before ending the thread. Since the thread can do an unbounded  
> computation in the finally blocks, or call Thread.ResetAbort to  
> cancel the abort, there is no guarantee that the thread will ever end.”
>
> http://msdn2.microsoft.com/en-us/library/ 
> system.threading.threadabortexception.aspx


So what happens if I throw an infinite loop into an exception handler?

Brian

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Daniel Bünzli]

Le 28 août 07 à 16:35, Brian Hurt a écrit :

>> http://msdn2.microsoft.com/en-us/library/ 
>> system.threading.threadabortexception.aspx
>
> So what happens if I throw an infinite loop into an exception handler?

It is written on the page. The thread does not terminate.

Daniel

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Robert Fischer]

Brian Hurt wrote:
> So what happens if I throw an infinite loop into an exception handler?
Now, my experience with .Net is somewhat dated, but I'm pretty sure it 
re-hangs on your loop, and signaling another abort will break out of 
your loop and continue up the chain of exception handlers.  At least 
once upon a time, there was a very large business which I worked for 
that did a lot of concurrent .Net work, and the standard solution was to 
keep signaling the abort until the thing finally died.

~~ Robert.

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Brian Hurt]

Robert Fischer wrote:

> Brian Hurt wrote:
>
>> So what happens if I throw an infinite loop into an exception handler?
>
> Now, my experience with .Net is somewhat dated, but I'm pretty sure it 
> re-hangs on your loop, and signaling another abort will break out of 
> your loop and continue up the chain of exception handlers.  At least 
> once upon a time, there was a very large business which I worked for 
> that did a lot of concurrent .Net work, and the standard solution was 
> to keep signaling the abort until the thing finally died.
>
> ~~ Robert.
>
>
Until you get someone "clever", who does something like (in Ocaml):

let rec do_my_work () =
    try
       do_a_bunch_of_work ()
    with
    | Thread_abort_exception ->
       (* Ack!  Someone tried to kill me!  I refuse to die! *)
       do_my_work ()
;;

I suppose eventually you'd blow stack.

Then, there's the what-if:

let rec example () =
    try
       do_a_bunch_of_work ()
    with
    | Thread_abort_exception ->
       raise (Invalid_arg "Ack!  They got me!")
;;

i.e. what happens if my catch expression raises another (different) 
exception?

Not to mention the fact that this solution requires a rather intrusive 
change to the run time, and a special exception which behaves 
differently from every other exception.

Brian

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Gordon Henriksen]

On Aug 28, 2007, at 11:12, Brian Hurt wrote:

> Robert Fischer wrote:
>
>> Brian Hurt wrote:
>>
>>> So what happens if I throw an infinite loop into an exception  
>>> handler?
>>
>> Now, my experience with .Net is somewhat dated, but I'm pretty  
>> sure it re-hangs on your loop, and signaling another abort will  
>> break out of your loop and continue up the chain of exception  
>> handlers.  At least once upon a time, there was a very large  
>> business which I worked for that did a lot of concurrent .Net  
>> work, and the standard solution was to keep signaling the abort  
>> until the thing finally died.
>
> Until you get someone "clever", who does something like (in Ocaml):
>
> let rec do_my_work () =
>    try
>       do_a_bunch_of_work ()
>    with
>    | Thread_abort_exception ->
>       (* Ack!  Someone tried to kill me!  I refuse to die! *)
>       do_my_work ()
> ;;

“Doctor, Doctor! It hurts when I go like this.”

You know the rest.

— Gordon

Re: [Caml-list] Has the thread cancellation problem evolved ?

[skaller]

On Tue, 2007-08-28 at 11:12 -0400, Brian Hurt wrote:
> Robert Fischer wrote:
> 
> > Brian Hurt wrote:
> >
> >> So what happens if I throw an infinite loop into an exception handler?
> >
> > Now, my experience with .Net is somewhat dated, but I'm pretty sure it 
> > re-hangs on your loop, and signaling another abort will break out of 
> > your loop and continue up the chain of exception handlers.  At least 
> > once upon a time, there was a very large business which I worked for 
> > that did a lot of concurrent .Net work, and the standard solution was 
> > to keep signaling the abort until the thing finally died.
> >
> > ~~ Robert.
> >
> >
> Until you get someone "clever", who does something like (in Ocaml):
> 
> let rec do_my_work () =
>     try
>        do_a_bunch_of_work ()
>     with
>     | Thread_abort_exception ->
>        (* Ack!  Someone tried to kill me!  I refuse to die! *)
>        do_my_work ()
> ;;
> 
> I suppose eventually you'd blow stack.
> 
> Then, there's the what-if:
> 
> let rec example () =
>     try
>        do_a_bunch_of_work ()
>     with
>     | Thread_abort_exception ->
>        raise (Invalid_arg "Ack!  They got me!")
> ;;
> 
> i.e. what happens if my catch expression raises another (different) 
> exception?
> 
> Not to mention the fact that this solution requires a rather intrusive 
> change to the run time, and a special exception which behaves 
> differently from every other exception.

That's when you have "ThreadReallyAbort" exception .. :))


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Lionel Elie Mamane]

On Tue, Aug 28, 2007 at 11:12:40AM -0400, Brian Hurt wrote:
> Robert Fischer wrote:
>> Brian Hurt wrote:

> Until you get someone "clever", who does something like (in Ocaml):

> let rec do_my_work () =
>    try
>       do_a_bunch_of_work ()
>    with
>    | Thread_abort_exception ->
>       (* Ack!  Someone tried to kill me!  I refuse to die! *)
>       do_my_work ()
> ;;

> I suppose eventually you'd blow stack.

Nah, that recursion is a tail recursion, so stack use doesn't grow :)

-- 
Lionel

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Gordon Henriksen]

On Aug 28, 2007, at 10:35, Brian Hurt wrote:

> Gordon Henriksen wrote:
>
>> Such problems are too common to ignore. .NET defuses them by  
>> treating  ThreadAbortException specially.
>>
>> “When a call is made to the Abort method to destroy a thread, the   
>> common language runtime throws a ThreadAbortException.   
>> ThreadAbortException is a special exception that can be caught,  
>> but  it will automatically be raised again at the end of the catch  
>> block.  When this exception is raised, the runtime executes all  
>> the finally  blocks before ending the thread. Since the thread can  
>> do an unbounded  computation in the finally blocks, or call  
>> Thread.ResetAbort to  cancel the abort, there is no guarantee that  
>> the thread will ever end.”
>>
>> http://msdn2.microsoft.com/en-us/library/  
>> system.threading.threadabortexception.aspx
>
> So what happens if I throw an infinite loop into an exception handler?

Such would fall into the category of “unbounded computation” in the  
quoted passage.

— Gordon

Re: [Caml-list] Has the thread cancellation problem evolved ?

[skaller]

On Sat, 2007-08-25 at 15:58 +0200, 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.  

BTW: unrelated issue: unloading the plugins. This presumably
will not be possible (since it isn't with bytecode either).
?

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Alain Frisch]

skaller wrote:
> BTW: unrelated issue: unloading the plugins. This presumably
> will not be possible (since it isn't with bytecode either).
> ?

Indeed, as far as I know, there is currently no plan to implement 
something like that.

-- Alain

Re: [Caml-list] Has the thread cancellation problem evolved ?

[Gordon Henriksen]

[-- Attachment #1: Type: text/plain, Size: 5383 bytes --]

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


[-- Attachment #2: Type: text/html, Size: 14066 bytes --]