[Bug java/24980] New: GCJ/GIJ segfaults on Workout.java from Click and Hack's "Java Puzzlers"

[Bug java/24980] New: GCJ/GIJ segfaults on Workout.java from Click and Hack's "Java Puzzlers"

[vadimn at redhat dot com]

GIJ segfaults on
java-puzzlers/5-exceptional-puzzlers/puzzle-45/Workout.java from Bloch
and Gafter's latest book.  (This "puzzle" is due to Jim Hugunin of
Jython and IronPython fame.)

| $ curl -O http://www.javapuzzlers.com/java-puzzlers.zip
|   % Total    % Received % Xferd  Average Speed   Time    Time     Time 
Current
|                                  Dload  Upload   Total   Spent    Left  Speed
| 100 61564  100 61564    0     0  37113      0  0:00:01  0:00:01 --:--:--
43957
| $ unzip -q java-puzzlers.zip 
| $ gcj -C java-puzzlers/5-exceptional-puzzlers/puzzle-45/Workout.java
| $ gij -classpath java-puzzlers/5-exceptional-puzzlers/puzzle-45 Workout
| Segmentation fault
| $ gcj --main=Workout
java-puzzlers/5-exceptional-puzzlers/puzzle-45/Workout.java
| $ ./a.out 
| Segmentation fault

The above is under the following version of GCJ:

| $ gcj --version
| gcj (GCC) 4.0.1 20050727 (Red Hat 4.0.1-5)
| Copyright (C) 2005 Free Software Foundation, Inc.
| This is free software; see the source for copying conditions.  There is NO
| warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

I also tried running this under three other 32-bit VMs: Sun 1.4.2_08,
BEA (build 1.4.2_05-b04), and IBM 1.4.2 (build cxia32142-20050609).

The only one that seems to run this program correctly is Sun's JVM.
(Given a limited maximum stack depth, the correct behavior for this
program is to run a few gazillion years and terminate successfully.
In Sun's case, the maximum stack depth is 1024 and the program can be
expected to run for about 10^300 years, give or take a few orders of
magnitude.)

IBM's 32-bit Linux JDK starts spewing out the following diagnostic:

| Stack overflow occurred outside JITted code or Interpreter.
| Searching for valid stack frames.
| Stack trace information below may not be accurate or complete.
|  It is provided for diagnostic purposes.
| Stack overflow occurred outside JITted code or Interpreter.
| Searching for valid stack frames.
| Stack trace information below may not be accurate or complete.
|  It is provided for diagnostic purposes.
|        at Workout.workHard
| Stack overflow occurred outside JITted code or Interpreter.
| Searching for valid stack frames.
| Stack trace information below may not be accurate or complete.
|  It is provided for diagnostic purposes.
|        at Workout.workHard

I had to Ctrl-C out of it after it generated 100,000+ lines of the
above.

BEA's JDK seems to do the right thing: run till the end of times.  On
closer inspection, it turns out to get a little hosed: it stops
responding to SIGTERM and SIGQUIT.

Bryce pointed out to me that Sun's behavior is not the only correct
interpretation of the above program's semantics.  If the runtime (or
the native ahead-of-time compiler) performs tail-call optimization,
then the program may loop forever without ever terminating.  After
thinking about this over the weekend, I came to realize that this is
wrong.  There seems to be no room for TCO in this particular case:

    private static void workHard() {
        try {
            workHard();
        } finally {
            workHard();
        }
    }

Note that while the recursive call in the "finally" block *is* in the
tail position, the call in the "try" block is not.  Therefore, the
recursion cannot be transformed into a loop.


-- 
           Summary: GCJ/GIJ segfaults on Workout.java from Click and Hack's
                    "Java Puzzlers"
           Product: gcc
           Version: 4.0.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: java
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: vadimn at redhat dot com


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24980

[Bug java/24980] GCJ/GIJ segfaults on Workout.java from Click and Hack's "Java Puzzlers"

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2005-11-21 21:18 -------
I think this is a dup of bug 1373.

You should try  with optimizations turned on.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24980

[Bug java/24980] GCJ/GIJ segfaults on Workout.java from Click and Hack's "Java Puzzlers"

[vadimn at redhat dot com]

------- Comment #2 from vadimn at redhat dot com  2005-11-21 21:20 -------
Created an attachment (id=10315)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=10315&action=view)
BinaryCallTree.java

For my own education, I wrote a variation of Workout.java that prints
out the call tree in the Graphviz dot format.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24980

[Bug java/24980] GCJ/GIJ segfaults on Workout.java from Click and Hack's "Java Puzzlers"

[vadimn at redhat dot com]

------- Comment #3 from vadimn at redhat dot com  2005-11-21 21:34 -------
Yeah, this may be a dup.

Bryce did mention that native-compiling this program with -O2 should
turn on the TCO.  There are two problems with this theory.  Number
one, it still segfaults for me:

| $ gcj -O2 --main=Workout Workout.java 
| $ ./a.out 
| Segmentation fault

This may be ok, because I'm using a rather old GCJ build.

Number two, the TCO cannot possibly be applied in this case.  (I can't
see how at the moment, but I'm willing to be convinced otherwise.)

Bryce ran the program under a newer version of GCJ and got some
equally bizarre results:

    public static void main(String[] args) {
        workHard();
        System.out.println("It's nap time.");
    }

In his case, it printed out "It's nap time."  This is incorrect,
because the program should either run out of stack and throw a
StackOverflowError, or it should it should run out of memory if stack
frames are allocated on the heap.  Under no circumstances can the
method return normally.  (I misspoke in my original post where I said
the program should, in theory, terminate successfully.)

So, yeah, if this is a dup, close it.  Note though this program
generates a much more interesting stress pattern than the one that aph
posted in bug 1373.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24980

[Bug java/24980] GCJ/GIJ segfaults on Workout.java from Click and Hack's "Java Puzzlers"

[vadimn at redhat dot com]

------- Comment #4 from vadimn at redhat dot com  2005-11-21 21:40 -------
Created an attachment (id=10316)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=10316&action=view)
call-tree-of-depth-4.png

So, speaking of stress patterns, this is what the call tree looks like
if you run attachment 10315 with the stack depth of 4.  In Sun's case,
it's a complete binary tree of depth 1024.

Blue arrows are calls made from within the "try" block.  Red arrows
are calls made from within the "finally" block.  Gray nodes are stack
overflow exceptions.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24980

[Bug java/24980] GCJ/GIJ segfaults on Workout.java from Click and Hack's "Java Puzzlers"

[pinskia at gcc dot gnu dot org]

------- Comment #5 from pinskia at gcc dot gnu dot org  2005-11-21 21:46 -------
(In reply to comment #3)
> Number two, the TCO cannot possibly be applied in this case.  (I can't
> see how at the moment, but I'm willing to be convinced otherwise.)

Actually TCO cannot because you still need to unwind the stack but it would
always be calling the first workHard, even before the finnally one is called..

>Bryce ran the program under a newer version of GCJ and got some
>equally bizarre results:

It is not that bizarre as what is happening is that the function is being
marked as a "pure" function so it does nothing useful, so we remove it. 

Anyways I am marking this as a dup of bug 1373.  This comes down to the halting
problem.


*** This bug has been marked as a duplicate of 1373 ***

*** This bug has been marked as a duplicate of 1373 ***


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |DUPLICATE


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24980

[Bug java/24980] GCJ/GIJ segfaults on Workout.java from Click and Hack's "Java Puzzlers"

[vadimn at redhat dot com]

------- Comment #6 from vadimn at redhat dot com  2005-11-21 21:52 -------
(In reply to comment #5)
> It is not that bizarre as what is happening is that the function is
> being marked as a "pure" function so it does nothing useful, so we
> remove it.

Except that under Bryce's GCJ, the function terminates successfully
even if you throw in System.out.println's into it, thus tainting its
"purity".


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24980

[Bug java/24980] GCJ/GIJ segfaults on Workout.java from Click and Hack's "Java Puzzlers"

[mckinlay at redhat dot com]

------- Comment #7 from mckinlay at redhat dot com  2005-11-21 22:02 -------
> Except that under Bryce's GCJ, the function terminates successfully
> even if you throw in System.out.println's into it, thus tainting its
> "purity".

No, when I add a System.out.println("hi"), and compile with a trunk gcj, the
example behaves as expected - "hi" is printed many times until a stack overflow
eventually occurs, resulting in a segfault. Removing the try/finally, the
example runs forever thanks to tail-call optimization.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24980