CSCE 314 Lecture 38

« previous | "Friday", December 5, 2011 | next »

Sample Type Hierarchy

For the following example, AnotherType <: MyType

Collection<?>
|-- Set<?>
|   |-- Set<MyType>
|   |-- Set<? extends AnotherType>
|   |   `-- Set<SubType>
|   `-- Set<? super Panda>
|       |-- Set<Panda>
|       `-- Set<Object>
`-- Collection<MyType>
    `-- Set<MyType>

Class File Format

Magic number: 0xCAFEBABE

Four data spaces:

1. Class area: code and constants
2. Java stack: "activation records" / "stack frames"
3. Heap: Where objects live
4. Native method stacks

Garbage collection

Follow all references from the current stack to the heap. Mark all reachable objects and delete everything that is not marked.

Verification Process

Ensures that class files follow certain rules

1. Does it follow the class file format
2. Are all constant references correct
3. Are instructions valid

.method public static addit([I)V
.limit stack 2
.limit locals 3
    iconst_0        // initialize running total: variable 1
    istore_1
    iconst_0        // initialize loop counter: variable 2
    istore_2
loop:
    aload_0         // if length of array is greater
    arraylength     // than the loop counter then exit the loop
    iload_2
    if_icmpge end
body:
    aload_0         // push array a
    iload_2         // push loop counter i
    iaload          // push a[i]
    iload_1         // push the sum computed so far
    iadd            // add them
    istore_1        // store result back to running sum
    iinc 2 1        // increment loop counter by 1
    goto loop       // start all over again
end
    return

Verifier follows code typing to check that stack is empty when entering loop, that stack size never exceeds 2, and that local variable count never exceeds 3, that the top element in the stack for arraylength is an array.

Verification Algorithm

1. Initialize stack picture to empty
2. Init local vars picture with type labels that correspond to method parameters and the rest with uninitialized
3. Mark the first instruction. Annotate with initial stack and local variable pictures
4. Choose a marked instruction. If none exist, method is OK
5. Do top elements of stack picture and local variable picture agree with instruction's expectations? if not, reject.
6. Draw new stack that results from current instructions. If stack is taller than .limit stack, reject.
7. Find follow-up instructions (next, if branches, goto target, exception handler)
8. For each follow-up instruction, if instruction is not annotated, do so
9. Unify pictures. reject if impossible.