[270] in java-interest
Re: Java & Recursion
daemon@ATHENA.MIT.EDU (David Hopwood)
Sat Jun 10 11:17:04 1995
Date: Sat, 10 Jun 1995 15:56:45 +0100
From: David Hopwood <david.hopwood@lady-margaret-hall.oxford.ac.uk>
Apparently-To: java-interest@java.sun.com
[Cc'd to java-interest@java.sun.com from comp.object]
In article <3r5nis$8pt@kaleka.seanet.com>,
Bob Atkinson <atkinson@atkinson.seanet.com> wrote:
>A question for the Java-literate:
>
>I notice in the security dicussion in the Java web page (sorry, don't
>have the exact reference handy)
<URL:http://java.sun.com/1.0alpha3/doc/security/security.html>
>that it is claimed that before Java will
>run downloaded code it will analyze first to ensure that, among other
>things, it will not cause stack overflows.
Unless I've got completely the wrong idea, it means overflows within a
particular method invocation or stack frame.
At each point in the code for a method, the type of each element of the stack
frame is known statically. Each bytecode instruction manipulates the end of
the stack in a known way.
(There is a list of the VM instructions in the Java Virtual Machine
Specification, at
<URL:http://java.sun.com/1.0alpha3/doc/javaspec/javaspec_1.html>).
An example is 'push a signed integer':
sipush item:
... => ..., item
If the type of the stack before the instruction was '...', afterwards it will
be '..., int' (where item is of type int).
There is a restriction on loops and conditional statements, that the stack type
at a jump must be the same as the stack type at the target of the jump.
This means you can't write code which compiles to:
LABEL: sipush 42
goto LABEL
because the stack type at the goto instruction is not the same as that at
LABEL. The compiler won't generate code like this, and the code verifier will
reject it.
(This also means you can't do things like copy a variable-length record or
array onto the stack - these must be heap-allocated).
Also, each method leaves the stack pointer in a consistent position relative
to where it was when the method was entered (there's an offset due to the call
parameters and result). This effectively means that the only place the stack
can overflow is on each method invocation, not within a method.
>If recursion is supported in the environment, this would seem to require
>solving the halting problem in order to accomplish.
Correct. Overflows due to a large number of nested method calls can't be
caught by the above method, so they are checked at run-time. I can still write:
void foo () { foo (); }
and this will eventually run out of stack space (but safely - the program
just halts with an error, it doesn't trash memory).
David Hopwood
david.hopwood@lmh.ox.ac.uk
-
Note to Sun employees: this is an EXTERNAL mailing list!
Info: send 'help' to java-interest-request@java.sun.com
