Writeup: Resolving differences between CS2030 notes and Oracle's JVM spec

[JuliaPoo]

Metadata

While reading the notes I had some discrepancies within the notes' description of the Java Virtual Machine (JVM), in particular Stack vs Heap, and my internal conception of what's happening, and attempted to resolve my understanding by consulting the JVM spec and disassembling the java bytecode. Upon doing so, I noticed significant discrepancies between what the notes present and the spec, and I attempt to resolve them here. I might be adding more if I have time and have more questions.

If there are any errors I made do point them out, I have no experience with the JVM prior to this.

Clarifications:

1. Am using the spec for SE19 simply bcuz that's what i have installed and I'm lazy to undo my installation for SE17. But otherwise, the concepts I'm talking abt here are fundamental to JVM and exists even way back in JVM7
2. When I say 'stack' and 'heap' and other objects, I'll be referring to these objects in the context of the JVM and not the analogue in native execution (E.g. JVM stack vs Native stack, JVM heap vs Native heap). This distinction is important cuz they don't necessarily coincide. JVM can allocate (jvm) stack frames in the native heap.
3. Will be talking abt execution that has no jitting, no entering native methods, no concurrency.

Preliminaries

• JVM is the object that executes java. Simplistically, Java source is compiled into Java Bytecode, which the JVM then executes. I consult the spec and the bytecode for this writeup.

The Stack: The notes VS the Spec

The Notes

The notes (Lecture 1) describe the stack as a "LIFO (Last In First Out) stack for storing activation records of method calls". In it, we see the stack containing the local variables for each nested method call. This conception aligns well with my intuition for the C-stack. However, it starts to break down when it comes to questions like

1. When exiting a method call (e.g., return), how does JVM know where to continue execution?
2. How does JVM know how much to pop from the stack upon exiting a method?
3. If the code is something like int a = x.length() + y.length(), how is the value of a computed?

The Spec

The Spec kinda agrees with the note's conception of the stack: JVM does have a LIFO stack that tracks method calls. However, each element in the stack isn't a local variable: Each element is a frame.

A frame is added when JVM enters a method, and removed when it returns from a method. Note, ONE frame is added to the stack PER method entered. Each frame, then contains a Local Variable Array and an Operand Stack. So at any point in time, a JVM thread manages at least TWO stacks: The stack that contains the frames (ill be calling this the Call Stack), and the current frame's operand stack. Note that the local variables of the current frame aren't in a stack: They are in an array.

When JVM enters a method, a frame is created and the Local Variable Array is populated with the method's arguments (E.g., calling f(a=1, b=2) adds (int a,1), (int b, 2) key-value pairs to the Local Variable Array). The Local Variable Array is also appended to during runtime (E.g., when executing int a = 1, and (int a, 1) key-value pair is added to the Local Variable Array). The operand stack, on the other hand, performs intermediate operations in computing the value of the local variables/return value. (E.g., a = 1+3, JVM uses the operand stack to compute 1+3 = 4 and stores the result in the Local Variable Array entry for a).

Aside: In class methods that have the this variable. Within JVM, the this variable, a reference to its class, is passed in as the first argument in the method, so the first element of the Local Variable Array in such a method is the (this, <reference in heap>) key-value pair.

The operand stack and local variable array can, of course, store references to objects in the heap as well, and the operand stack can store references to the local variable array. Do note that these are only in the current frame. To my knowledge, there isn't a way for a current frame to directly access the operand stack/local variable array of another frame.

When JVM exits the method, the return value is passed to the previous frame somehow (idk how) and the current frame is removed. Execution continues in the previous frame.

Refer to Here for an incomplete visualisation of what I mean (The link visualises the Call Stack and the Local Variable Array but not the Operand Stack, and doesn't account for everything, like inner classes).

Aside: The spec describes JVM as both a Register Machine and a Stack Machine. The Local Variable Array is serving the function of the Registers in a Register Machine. The Operand Stack serves as the Stack in a Stack Machine. Here's a brief example of how the JVM Operand stack works:

Suppose we have the following code:

class B {
  int f() {
    int a = 1;
    int b = 2;
    int c = a + b;
    return c;
  }
}

The corresponding disassembly looks like this:

B.f Bytecode
    0: iconst_1     // Loads constant `1` onto the Stack
                    //      Operand Stack: [1]

    1: istore_1     // `op_stack` is popped to `localvar` array at index 1 (var `a`). 
                    //      Operand Stack: []

    2: iconst_2     // Loads constant `2` onto the Stack
                    //      Operand Stack: [2]

    3: istore_2     // `op_stack` is popped to `localvar` array at index 2 (var `b`).
                    //      Operand Stack: []

    4: iload_1      // Pushes to `op_stack` from `localvar` array at index 1 (var `a`)
                    //      Operand Stack: [1]

    5: iload_2      // Pushes to `op_stack` from `localvar` array at index 2 (var `b`)
                    //      Operand Stack: [1,2]

    6: iadd         // Pops the last two elements of `op_stack`, adds them and pushes the result back
                    //      Operand Stack: [3]

    7: istore_3     // `op_stack` is popped to `localvar` array at index 3 (var `c`). 
                    //      Operand Stack: []

    8: iload_3      // Pushes to `op_stack` from `localvar` array at index 3 (var `c`)
                    //      Operand Stack: [3]

    9: ireturn      // Pops last element of the current `op_stack` and pushed into the `op_stack` of the previous frame
                    //      Operand Stack: []

Attempt to resolve

Here are the main 3 concerns I have when I saw this discrepancies:

1. The notes shows the stack containing local variables but the spec shows the Call Stack consisting of objects called frames, which are more complex objects containing other objects of relevance during the execution of a method
2. The notes imply the local variables are part of a stack. In reality, they are part of an array. This has significance in how one reasons about how operations are carried out
3. The notes raises a lot of questions

I feel like the stack as described in the notes combines the Local Variable Array of all frames on the call stack into one big stack, with the order on the stack being the order in which the variables are created? This is a very liberal interpretation of the spec and I have no idea how to resolve this discrepancy.

Accessing variables that isn't in the Local Variable Array

Okay, so each frame's code can access the Local Variable Array, which includes method arguments. But as we know, code within a method can access way more than that. E.g.,

class B {
  void f() {}
}

public class Main {
  public static void main(String[] args) {
    B b = new B();
    b.f();
  }
}

Within Main.main, the symbols B and B.f are not in Main.main's Local Variable Array, and yet they can be accessed.

The solution is in the Constant Pool. Each frame has its own Constant Pool that contains all references to symbols that the frame should be able to access, but isn't a local variable or an argument. E.g., for the example above we have:

Main.main Constant Pool:
     #1 = Methodref          #2.#3          // java/lang/Object."<init>":()V
     #2 = Class              #4             // java/lang/Object
     #3 = NameAndType        #5:#6          // "<init>":()V
     #4 = Utf8               java/lang/Object
     #5 = Utf8               <init>
     #6 = Utf8               ()V
     #7 = Class              #8             // B
     #8 = Utf8               B
     #9 = Methodref          #7.#3          // B."<init>":()V
    #10 = Methodref          #7.#11         // B.f:()V
    #11 = NameAndType        #12:#6         // f:()V
    #12 = Utf8               f
    #13 = Class              #14            // Main
    #14 = Utf8               Main
    #15 = Utf8               Code
    #16 = Utf8               LineNumberTable
    #17 = Utf8               main
    #18 = Utf8               ([Ljava/lang/String;)V
    #19 = Utf8               SourceFile
    #20 = Utf8               Main.java

Main.main bytecode:
    0: new           #7                  // class B
    3: dup
    4: invokespecial #9                  // Method B."<init>":()V
    7: astore_1
    8: aload_1
    9: invokevirtual #10                 // Method B.f:()V
    12: return

Do note that in the Constant Pool, not all symbols have been 'initialised'. E.g., In the above, the spec totally allows #7 (a reference to class B) to reference nothing UNTIL Main.main needs it, at which point the file B.class will be loaded into memory and #7 is made to reference class B.

Inner Classes: Heap layout explanation

The Notes

Consider this snippet from Recital 7 and the heap layout claimed:

abstract class A {
  abstract void g();
}

class B {
  int x = 1;
  void f() {
    int y = 2;
    A a = new A() {
      void g() {
        x = y;
      }
    };
    a.g();
  }
}

This immediately raises a few questions regarding the heap object A:

1. Why is y variable duplicated in the stack AND the heap (as part of abstract class A). Couldn't a.g simply access y via the stack?
2. Why does A have a reference to its outer class B.this in the heap when it could similarly access B.this in the stack?
3. If y is duplicated, why isn't B.this.x duplicated?

The Spec

We can dump the heap layout when executing a.g to see that the note's heap layout is essentially correct.

What's happened here is that, in B.f, the inner class is internally represented as B$1 extends A:

class B$1 extends A {
  final int val$y; // <-- Duplicated y value from the stack
  final B this$0; // <-- Reference to outer class B (B.this)
  B$1(B, int); // <-- Attributes are passed in via the constructor
  void g();
}

Here's my reasoning for the 3 questions mentioned above:

1. The y in B.f lives within B.f's frame in the Local Variables Array. Since the frame for a.g is different than B.f, a.g is unable to access the variable y from B.f's frame. It hence has to be passed as an attribute into the inner class B$1.
2. Since the java language allows one to access the outer class from an inner class via B.this, a reference to the outer class is similarly passed as an attribute into the inner class B$1 by default.
3. There is no need for B.this.x to be duplicated as a property of B$1 because it is already accessible via B.this.

Subclasses: Heap layout explanation

The Notes

Consider the code

class Circle {

  protected final double radius;

  Circle(double radius) {
    this.radius = radius;
  }
}

class FilledCircle extends Circle {

  private final int color;

  FilledCircle(double radius, int color) {
    super(radius);
    this.color = color;
  }

  FilledCircle fillColor(int color) {
    return new FilledCircle(super.radius, color);
  }
}

The notes show that the heap layout for FilledCircle is a 'merge' of both itself and it's superclass:

Note that I changed the class Color to int to make things easy.

The Spec

We can similarly dump the heap to see that the notes pretty much agree with the spec:

So unlike how inner classes are dealt with (i.e., via having a reference to its outer-class as an attribute), inheritance is dealt with by simply merging the heap layout of the superclass and itself as a single entry.

TODO if have time and motivation

1. How return works: How the JVM knows where to continue execution upon exiting a method

Overall Questions

1. Why does CS2030 teach the JVM when Java is already a pretty good abstraction from its VM and bytecode (e.g., C/C++ isn't)? Some questions like the inner class example in Recital 7 seem impossible to reason about without knowing details absent from the notes.

Resources

1. JVM Spec
2. Java Bytecode
3. Incomplete JVM Stack Frame Visualiser
4. Javap: Disassembler Reference API
5. Visualise JVM stuff including heap

[errantSquam]

Plugged the code from the recitation into the [visualization](https://cscircles.cemc.uwaterloo.ca/java_visualize/#code=public+class+ClassNameHere+%7B%0A+++public+static+void+main(String%5B%5D+args)+%7B%0A++++++abstract+class+A+%7B%0A+++++++++abstract+void+g()%3B%0A++++++%7D%0A%0A++++++class+B+%7B%0A+++++++++int+x+%3D+1%3B%0A%0A+++++++++void+f()+%7B%0A++++++++++++int+y+%3D+2%3B%0A%0A++++++++++++A+a+%3D+new+A()+%7B%0A+++++++++++++++void+g()+%7B%0A++++++++++++++++++x+%3D+y%3B%0A+++++++++++++++%7D%0A++++++++++++%7D%3B%0A%0A++++++++++++a.g()%3B%0A+++++++++%7D%0A++++++%7D%0A%0A++++++B+b+%3D+new+B()%3B%0A++++++b.f()%3B%0A+++%7D%0A%7D%0A%0A&mode=display&curInstr=20), for anyone who wants to try it.

Visualization vs. Recitation

Would like more elaboration on what the disrepancy is. Might be because it's late and I'm not following too well. Is it the lack of frames (in the recit) as opposed to the JVM very clearly separating frames per method?

[JuliaPoo]

I'll be writing up on how the JVM deals with inner classes. The simulation I linked is incomplete and hence ur screenshot of it is also incomplete. From what I gather, the note's heap layout for the instance of abstract class A is accurate. The reason why it assumes such a layout however, is never mentioned in the notes and I'm guessing we are somehow meant to infer why. (E.g., we are meant to ask ourselves and answer questions like, why is y duplicated in the JVM? Like why can't the method a.g simply access the variable y from the stack shown in the notes)

[errantSquam]

Yeah, that's a good point tbh. Also I double checked SE17 (the one we're using) vs. SE19 (your reference) docs, and both are identical with regards to the JVM stack.

My thoughts, as discussed in Telegram already:

From the recit, it does seem like they're drawing the stack in

1. order of frames introduced
2. order of local variables introduced, for each frame. additionally, these are actually the pointers and not actually the variables themselves (as they are stored in some other array of constants)

I do agree that mentioning frames (and maybe the operand stack) may have been a clearer way to illustrate the JVM stack. Would like to know prof's thoughts on this. Maybe because 2040 is separate from 2030 that it's not gone into detail so as to not confuse students? Idk. Frames could be a nice resource for folks who want to do further reading in the future.