[e-lang] Non-local Exits vs Defensive Consistency - David Hopwood

Mark Miller erights at gmail.com
Sun Jan 28 23:06:56 CST 2007 

---------- Forwarded message ----------
From: David Hopwood
Date: Jan 27, 2007 10:07 PM
Subject: Defensive consistency and exceptions


[BTW, I think we should move this discussion to e-lang. Really, it should
have been there all along. After coming into this discussion 4 posts in, my
head almost exploded from trying to simultaneously think about four proposals
from DavidW, one from Alan and one from MarkM. The longer we leave it, the
more incomprehensible it will get to anyone on e-lang who wants to follow
the arguments in detail. Perhaps MarkM can post a summary there to start
with.]

Mark Miller forwarded:
> ---------- Forwarded message ----------
> From: Close, Tyler J.
> Date: Jan 26, 2007 3:54 PM
> Subject: VirtualMachineError
>
>
> At the Friday morning cap meeting today we spent a lot of time thinking
> about programming for defensive consistency in Joe-E, in the presence of
> VirtualMachineError. The conclusion was that it's not feasible with the
> current Joe-E rules, and some form of amendment is needed.

I agree, but I would go further. For defensive consistency to be practical,
it must be composable; that is, if you have defensively consistent abstractions
A_1...A_n, then you must be able to compose them to produce a defensively
consistent abstraction B that uses A_1...A_n.

Suppose that an operation on A_i can fail in such a way that the operation
has side-effects on A_i's state. Since A_i is by assumption defensively
consistent, the new state satisfies the conditions for A_i to be consistent.
However, it doesn't satisfy the conditions for B to be consistent.

B can catch the exception caused by the failure. In specific cases, it can
probably undo the state change to A_i, or if necessary, throw away the
instance of A_i and create a new one that makes B's state consistent again.
So, if I show you any particular piece of code that fails to be defensively
consistent when an abstraction that it uses throws an exception, you can
almost certainly fix it. After all, I've just shown you where the bug is.

Now, what if I tell you to write or review a library or application that
has 100,000 lines of code in thousands of abstractions, and convince me
that the whole thing is defensively consistent whenever it needs to be?
That's a task of a quite different order of difficulty, and unfortunately,
it is this kind of task that we need to be able to deal with -- not just toy
examples.

To address this problem, you have to consider all possible places (many of
them implicit) where an exception could be thrown in that 100,000 lines, and
make sure that consistency is recovered in all cases. And you must somehow
convince me that there are no bugs in the recovery code, even though it will
be poorly tested because it's only invoked in failure situations, and even
though this code must itself perform operations that can fail.

While exceptions that can be thrown at any time, like VirtualMachineError
in Java, are a particularly obvious example of the difficulty, in fact *all*
exceptions -- or more generally, all failure conditions -- present difficulties
to some extent. (Note that signalling failures in some other way than by
exceptions wouldn't really help.)

I am not saying that it is necessary to achieve perfect defensive consistency,
in order for any degree of defensive consistency that is achieved to be
beneficial. At the least, it should help reliability, even if some exploitable
security bugs remain. However, perfect defensive consistency has to be the goal
that we aim for, even if we don't succeed.

Having thought about this problem a lot since MarkM's thesis was published, I've
concluded that defensively consistent programming on a large scale is
unreasonably
difficult without language support for atomic transactions.
Transactions move the
responsibility for cleaning up after a failed operation onto the
language, rather
than requiring the application programmer to know when and how to do
it correctly.

This support needs to be integrated with the semantics of exceptions (and
other non-local exits if the language has them) in such a way that the *default*
behaviour for a non-local exit is secure in as many cases as possible. We also
need to be able to find cases where this isn't possible (because there are
side-effects that can't be rolled back), so that we can concentrate more review
effort on those areas. I will make a concrete proposal for transaction support
in event-loop languages in the next few days.

> Any allocation could cause a java.lang.OutOfMemoryError. Memory
> allocations happen frequently in Java and often implicitly, either due
> to Java syntax, or predefined APIs, like java.lang.reflect.Proxy which
> allocates an array for the invocation arguments. When such an error
> occurs, the right thing to do is to abort the current transaction
> entirely. Unfortunately, we don't have a convenient way of expressing
> this logic if our caller can catch a VirtualMachineError. By catching
> such a VirtualMachineError, the caller could trap the callee in an
> inconsistent state. For example:
>
>    this.a = ...    // Initial update step
>    new Object()    // OutOfMemoryError
>    this.b = ...    // Final update step not done
>
> In some cases, it might not be possible to structure the code such that
> all allocations happen before all variable updates. Even if it were
> possible, it would be awfully error prone.
>
> We went through a bunch of proposals for fixing this before deciding
> that the best thing to do is forbid catching of a VirtualMachineError,
> and forbid finally clauses (since they can result in a
> VirtualMachineError being silently dropped).

This is related to another problem with the semantics of finally clauses,
mentioned in <http://www.eros-os.org/pipermail/e-lang/2006-July/011371.html>.

That is, if you have code that does:

  try {
      throw foo;
  } finally {
      throw bar;
  }

then the effect in both Java and E is to forget that 'foo' was thrown, and
throw 'bar' instead. My interpretation is that this the wrong thing regardless
of which exceptions 'foo' and 'bar' represent, because it loses information
about what caused the failure. The fact that in full Java you can't prevent a
VirtualMachineError (or any other kind of exception) from being silently
dropped  is a symptom of this loss of information.

(<http://www.antlr.org:8080/pipermail/antlr-interest/2006-March/015668.html>
is talking about essentially the same thing. It's even scarier when you
realise that, in full Java, the convoluted code suggested there still doesn't
solve the problem, because an asynchronous exception can happen in the second
'catch(Throwable t)' block. At least neither Joe-E nor E have asynchronous
exceptions.)

Anyway, I suggest that anyone who wants to talk about this issue with finally
clauses (which is less serious than the main problem we're discussing), should
start another thread on e-lang.

> We found coding idioms to
> replace the common uses of finally clauses, so that although extreme,
> this loss is survivable.
>
> The finally clause could be added back to Joe-E if MarkM's JSR
> suggestion for adding a Keeper API to Java goes through.

I must have missed that. I don't see it at <http://jcp.org/en/jsr/all>, or
any mention of it in the e-lang archives.

MarkM wrote:
> After Tyler sent his message, Alan Karp came up with a less severe proposal:
>
> * Have Joe-E outlaw the catching of Errors.
> * Have Joe-E require all try-finally code to follow the following boilerplate:
>
>    try {
>        stuff1 // only normal Joe-E restrictions
>    } finally {
>        try {
>            stuff2 // no non-local exit via return, break, continue, or goto
>        } catch (Exception ex) {
>            throw new Error(ex)
>        }
>    }

I don't see how this solves the original problem as described by MarkM:

>> [...] the caller could trap the callee in an inconsistent state. For example:
>>
>>    this.a = ...    // Initial update step
>>    new Object()    // OutOfMemoryError
>>    this.b = ...    // Final update step not done

try {
    callee.m();
} finally {
    try {
        // callee may be in an inconsistent state here, which we can exploit
    } catch (Exception ex) {
        throw new Error(ex); // too late, doesn't help
    }
}

I don't think that David Wagner's proposals (with the correction from MarkM
about not creating direct subclasses of Throwable) have the same flaw.

David Wagner wrote:
> Forbidding 'finally' [in order to avoid silent dropping of VirtualMachineError]
> is pretty devastating and seems out of proportion.

I agree.

> (I once heard the advice that in well-written code, you may see ten times
> as many 'finally' clauses as 'catch' clauses.  That resonated with me.)
>
> The solution MarkM had recommended earlier was a VM modification to cause
> the VM to terminate immediately rather than throwing a VirtualMachineError.

I also think that causing the VM, or at least the current thread, to terminate
immediately is the only approach that will work (short of making more
significant
language changes such as introducing transactions).

Whether you do that by modifying the VM, or by imposing some restrictions on
programs so that the existing Java semantics causes the thread to terminate
(as in your proposals #1-3), seems like a secondary consideration to me.

BTW:
>    catch (VirtualMachineError e) {
>        java.lang.Runtime.getRuntime().halt(1);
>    }

could be:
    catch (VirtualMachineError e) {
        org.joe_e.Utility.fatalError();
    }

but I don't think this is better than "Dave's proposals #1-3".
Forget I mentioned it :-)

MarkM wrote:
> I agree that the issue is only critical for VirtualMachineErrors.

I don't. While it is effectively impossible to maintain defensive consistency
in the face of VirtualMachineErrors, it is still *too difficult* to maintain
it in the face of other exceptions that can be thrown implicitly. In Java or
Joe-E that includes many RuntimeExceptions, as well as Errors.

>From the "Direct Known Subclasses" of RuntimeException listed at
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/RuntimeException.html>,
at least [Arithmetic, ArrayStore, ClassCast, IndexOutOfBounds,
NegativeArraySize,
NullPointer, TypeNotPresent]Exception can be thrown implicitly by language
operations other than method calls.

In addition, any RuntimeException can be thrown by a method call. The API
description of RuntimeException says that it is "the superclass of those
exceptions that can be thrown during the normal operation of the Java
Virtual Machine."

[Incidentally, while I'm looking at this documentation, Throwable.initCause
is a non-obvious and undesirable source of mutable state in all
exception objects.
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Throwable.html#initCause(java.lang.Throwable)>.]


I have more to say, but I'll leave it there for the time being.

--
David Hopwood <david.nospam.hopwood at blueyonder.co.uk>

More information about the e-lang mailing list