- Special Edition Using Java, 2nd Edition -

Chapter 36

Inside the Java Virtual Machine

by Jordan Olin

The concept and implementation of virtual machines (VM) have been around for quite some time. One of the earliest commercial environments with this architecture was the UCSD p-System. This system was created by Dr. Kenneth Bowles at the University of Southern California, San Diego, in the 1970s. Dr. Bowles was able to spin off a company to market the operating system called SofTek Microsystems. In fact, the p-System was the core operating system for the Apple ///. It was also the alternative operating system to PC-DOS for the IBM PC after the PC’s introduction in 1980.

Like the Java environment, the UCSD p-System was based on a primary language (Pascal). The UCSD p-System had a set of primitive core libraries, a machine-independent object file format, a set of byte-oriented pseudocodes, and a virtual machine definition to interpret them. The p-System and its version of Pascal even had advanced features such as a full-screen user interface, concurrency primitives, and a dynamic library mechanism called units. The p-System was ported to many architectures and had wide-spread success in the vertical software market.

So, if the p-System was so much like Java, why isn’t it still around today? When I asked Sun’s chief technology officer, Eric Schmidt, this question, he simply replied, “Have you ever known a university that knew how to market software?” The point of this is that Java is not so unique or new. The Java environment is a success because it has the sponsorship of a very successful company and a much more mature industry.

• The architecture of the Java Virtual Machine
• The JVM is an engine that knows how to execute the instructions in your .class files, known as Java bytecodes. You review some of the major processes of the JVM, such as verification, the interpreter loop, and garbage collection. A detailed description of the current Java bytecodes is included at the end of this chapter.
• Memory management and garbage collection
• Class file verification
• The JVM bytecodes

Elements of the JVM

When you look at the Java environment, you see five major elements:

• Java language
• Java/Sun core class libraries
• .class file structure
• Bytecode definitions
• JVM specification

Of these items, the last three are really what enabled Java technology to become as widespread (or ubiquitous) as quickly as it has. Thus, the designers of Java gained almost instant portability of any .class file to any computer/chip-set with an implementation of the JVM. This portability applied regardless of what kind of host computer/chip-set was used to compile the source. The concept of “write once, run anywhere” is being realized because of the widespread implementation of the JVM on a wide array of hardware platforms and architectures.

The remainder of this section describes some of the technical details involved with Sun’s implementation of the JVM. Clearly, many vendors have created JVM implementations (Natural Intelligence, Netscape, Microsoft, and more). All of the vendors have contributed some unique features to their implementations. But, what is fundamentally important is that they all support Sun’s initial specification for the “.class” file structure, bytecode definitions, and virtual machine.

The Architecture of a Virtual Machine

So, what really is a virtual machine? It is a software concept that is based on the notion of an imaginary computer with a logical set of instructions, or pseudocodes, that define the operations this computer can perform. A VM-oriented compiler will typically take some source language. Instead of generating machine code instructions targeted to a particular hardware architecture, it generates pseudocode streams that are based on the imaginary computer’s instruction set.

The other side of the equation is how these instructions get executed. This is where an interpreter, or what the Java world has been referring to as the virtual machine, takes its role. An interpreter is really just an application that understands the semantics of the pseudocodes for this imaginary computer and converts them to machine code instructions for the underlying hardware to which the interpreter has been targeted. The VM also creates a runtime system internally to support implementing the semantics of the instructions as they are executed. The runtime system is also responsible for loading object (or .class) files, memory management, and garbage collection.

Because of the inconsistency in the hardware platform facilities that are used to host a VM, they are typically based on the concept of a stack machine. A stack machine does not use any physical registers to pass information between instructions. Instead, it uses a stack to hold frames representing the state of a method, operands to the bytecodes, space for arguments to the methods, and space for local variables. There is one pseudoregister called the program counter—a pointer into the bytecode array of the currently executing instruction.

The actual logic for the interpreter phase of the VM is a very simple loop. The following diagram represents a flowchart view of the logic that is typically used by a stack-based VM interpreter.

FIG. 36.1

The JVM interpreter loop.

There are two important points to note about how the interpreter actually processes the bytecode instructions:

• The majority of all semantic routines that perform the action associated with a given bytecode get their operands from the stack and place their results back on the stack.
• The actual bytecodes will typically have arguments that are in line in the bytecode stream immediately following the bytecode itself.

For example, there are bytecodes that push values from the Constant Pool onto the stack. These bytecodes have, as an argument, the index of the value in the Constant Pool. When the semantic for that bytecode is complete, the value will be on the top of the stack, and the Program Counter will point to the bytecode immediately following the argument. Here is what the bytecode stream might look like for the Load Constant-2 Bytecode:

ldc2 index byte 1 index byte 2 <next bytecode>

Something else that may not be readily apparent is that method calls, exception handlers, and monitors (the locks used by the synchronize language keyword) are all handled by specific bytecodes. They are not the responsibility of the interpreter loop itself. The loop is very stupid in that all it knows how to do is to get a bytecode and fire off its associated semantic routine.

Finally, there are other techniques that an interpreter may use to process the stream of bytecodes representing the executable instructions for the VM. One common optimized interpreter technique is called a threaded interpreter (not to be confused with multithreading). A threaded interpreter does not use a loop-based approach to traverse the stream of bytecodes. Instead, the interpreter actually jumps from bytecode semantic to bytecode semantic in a similar way that a needle and thread are used to make stitches. The big advantage to this technique is that there is no overhead for the interpreter loop, the instructions are executed, and a simple jump is performed at the end. As this is an implementation choice, it does not affect the .class file structure and, hence, is an option open to people developing their own VMs.

The other optimization that is becoming increasingly popular is the use of what is called a Just-In-Time compiler, or JIT compiler. The Microsoft JVM, Microsoft Internet Explorer 3.0, and Netscape Navigator 3.0 all include JIT technology. The idea of the JIT compiler is that instead of interpreting each instruction of the bytecode stream, the set of bytecodes is directly translated into an equivalent set of machine code instructions for the target system at runtime. This new translated machine code version of the method is then stored and used whenever a call is made to that particular method. So, you get the portability based on the .class file and bytecodes. You also get close-to-native code performance after taking the one-time, up-front translation from bytecode to machine code.

Now that you have a better feel for the architecture of the VM, let’s examine how it deals with memory management.

Memory Management and Garbage Collection

One of the major decisions that implementers of runtime systems face is how to handle dynamic memory requirements that are placed on the systems by the programs that are executing within them. The runtime system designer must choose between making the user of the system responsible for memory management or making the runtime system smart enough to handle this task.

If you have ever coded in any compiled 3GL such as C, C++, or Pascal, then you have experienced the “pleasure” of handling your own memory management. These languages have runtime systems that give you primitive methods for allocating and deallocating arbitrarily sized blocks of memory from a larger chunk of memory called a heap. Allocating your application’s memory needs from the heap is not a problem if your application has relatively few dynamic memory requirements, but most object-oriented applications tend to create and destroy relatively small objects on a frequent basis.

In order to help deal with this problem, most runtime systems have a heap manager that actively maintains the heap in a state where memory is available as much as possible. One of the major problems that the heap manager tries to solve is called fragmentation, which is a result of allocating and deallocating lots of small, nonuniform pieces of memory from the heap. Typically, a heap is managed by tracking memory in two lists:

• Free block list
• Allocated block list

When a request is made to the heap manager for a chunk of memory, the free list is searched for a block that can fulfill this request. Most modern heap managers keep the free list in ascending order of the free blocks’ sizes. This allows the allocation mechanism to use a “first-fit strategy,” finding the first-available, smallest block of memory that can satisfy the request. This strategy helps keep fragmentation of the heap to a minimum.

Another technique that heap managers use to keep fragmentation of the heap to a minimum is called coalescing. As memory is returned to the heap, a new block is placed in the free list. As this process occurs, the free list is examined to see if the piece of memory being returned immediately precedes or follows another free block. If this is the case, then the two blocks are merged together, creating one larger free block.

Another issue in heap management is how to deal with a request for more memory than an individual block on the free list can provide. Such a request requires that the heap manager take some very proactive steps in order to create more memory. The solution is a technique called compaction. Compaction is the process of merging all free blocks together by moving the allocated memory (memory between the free blocks) to one end of the heap, thereby creating one large, coalesced free block. The real difficulty with this process is that the runtime system must know the location of every variable (stack-based or dynamic) that refers to any heap-based object in memory. The system must then update the variable with the new location of the object that it refers to. This process is very expensive in both time and memory overhead, but compaction is a reality in any heap-based allocation system.

The other major problem with being responsible for your own memory allocation and, specifically, deallocation is the concept of dangling references, or garbage. This refers to objects in memory that you allocated but have lost the reference (or pointer) to, so you cannot explicitly de-allocate the memory. Dangling references are very easy to create. The following C++ code shows a typical way to create a dangling reference:

int *iArray;
// Create initial array
iArray = new int[3];
…
// Grow the array
if (iArrayCount == 3) {
int *tempArray = new int[6];
for (int i = 0;i < 3;++i) tempArray[I] = iArray[I];
// MAKE A DANGLING REFERENCE:
iArray = tempArray;
}

Once iArray is overwritten with tempArray, the memory chunk originally pointed to by iArray is orphaned and now garbage. The memory chunk cannot be reclaimed during compaction, as it is not on the free list. The only way to deal with this situation is via garbage collection.

Garbage collection is a technique in which all allocated memory objects that are no longer needed or referred to may be reclaimed back to the free list without an explicit de-allocation. It is a process of the heap management system, and memory blocks must be structured in specific ways to take advantage of it. Two common garbage collection techniques can be used: reference counting, and mark and sweep.

Reference counting requires that each object instance in the heap maintain a field called the reference count. As a field or variable is assigned a reference to an object, that object’s reference count is increased by one. When the field or variable that refers to the object goes out of scope or is destroyed, the reference count is decreased by one. When an object’s reference count reaches zero, it is no longer in use and its space may be collected. This algorithm is fast during collection but has a performance penalty when any assignment is without objects or an object is passed as an argument. For each of these situations, the reference count must be maintained at runtime, causing general slow-downs of the runtime system.

The mark and sweep algorithm requires that each object contain a bit field called the mark bit, or it is required that an external array is created when the algorithm runs to hold the mark bit. The algorithm begins by traversing all allocated blocks of memory in the heap and resetting the marked bit for that block. Next, examine all fields and variables that refer to objects in the heap, setting the marked bit of the heap object to true. Finally, sweep through the allocated heap objects and look for any that are not marked. Then, either reclaim the space by putting the unused objects on the free list, or copy the “live” objects to the end of the heap. Then, reclaim the original area back to the free list and compact (a variant of mark and sweep known as stop and copy). This algorithm has low storage overhead and does not affect runtime performance overall but may cause longer-than-desired lags in time when the garbage collector runs.

Now that you can see how difficult a problem heap and memory management can be, especially for the non-Java developer, let’s take a look at how the Java runtime system handles these problems.

First, the JVM uses two separate heaps for dynamic and static memory allocation. All class definitions, the Constant Pool, and method tables are kept in a nongarbage collected heap. So, once a class definition has been read in, the structural information and methods stay in memory. This does add a little storage overhead but improves performance for classes that come and go relatively frequently within an application.

The second heap is split into two areas that grow in opposite directions. One area is used to hold object instances, and the other contains “handles” to those instances. The runtime image of fields and variables in your Java application that reference object instances do not actually contain pointers to those objects. They contain pointers to a special, fixed-size, heap-based memory object called a handle. The handle is a structure that contains two pointers, one to the object’s method table and the other to the actual object instance. The advantage to this layout is that the handles never move in memory, so there is never a need to keep track of which variables point to which objects when updating pointers after compacting. You simply update the pointer value of the handle structure.

The object space of the heap is managed in a traditional fashion in that there is a free list and an allocated object list. As objects are instantiated, the free list is searched for the “first-fit block.” Also, if possible, coalescing happens during this phase (as opposed to when an instance is put back on the free list) in order to make the garbage collection process faster. In addition, the dangling reference problem is eliminated by Java, as you are not responsible for explicit object deallocations. The Java language has a new operator but no corresponding delete.

The garbage collection algorithm used by the Java VM applies to all objects in the dynamic heap. The algorithm runs synchronously whenever the heap manager cannot find any memory in the free space list. Or, it may also run asynchronously in that a thread for the garbage collector is kicked off whenever the system is idle for a sufficient period of time. (This is of dubious value, as the asynchronous garbage collector will be interrupted and have to start again if a runnable class becomes ready.) And, you may manually initiate the garbage collection algorithm by calling the method System.gc(). For highly interactive applications where idle processing may be at a minimum, you might occasionally want to call the garbage collector manually.

The actual garbage collector used by the JVM is an implementation of the stop-and-copy algorithm. But, there is a difference. Normally, after the garbage collector finishes its compaction phase, all variables and fields that relate to an object would need to change. But, because all object reference variables are handle based, we don’t need to find and update all variables that point to active objects. You can simply update the handle in the heap to point to the just-moved object instance. The algorithm is pretty fast but not ready for real-time applications.

One last aspect to the JVM’s garbage collector is the notion of a Finalizer method. A Finalizer is a special method called finalize that is declared in the base class java.lang.Object. It has the following prototype:

protected void finalize () throws Throwable;

The finalize method is for cleaning up external resources (such as open files) that would not normally be performed in routine garbage collection. The garbage collector calls the finalize method just prior to garbage collecting an object instance. The problem is that garbage collection is not run immediately when you call the System.gc() method; it is simply scheduled to run. The garbage collector thread runs at a very low priority and may get interrupted frequently. In fact, the garbage collector may never get to dispose of your object before the application terminates. So, generally speaking, the usefulness of implementing the finalize method is questionable.

You can do one other trick in a finalize method—”resurrect” an object instance. It is possible for you to place the value of the this field into some other object reference and stop the object from being garbage collected. At that point, though, the garbage collector will not call the finalize method again, even when the object instance is really ready for garbage collection.

That’s all there is to heap management in Java: one heap contains a fixed table of class information and methods, and another heap holds the handle table and object instances. You don’t explicitly deallocate anything (although setting an unused object variable to null will act as a hint to the garbage collector and heap), and the garbage collector may be run manually by calling System.gc().

Class File Verification

The last real algorithm that I cover for the JVM is verification. Verification is a process that is applied to certain class files as they are loaded. Because Java is oriented toward applications whose pieces (.class files) are potentially scattered anywhere around the globe, you need a mechanism that can prove these nonlocal classes can be properly executed by the JVM. By default, the java command will put all classes that were not loaded from the local hard drive through the verification process. Whether a class is put through the verification process is a function of the Class Loader and is controlled by arguments that you may specify on the java command line. In the case of browsers that support Java applets, all nonsystem classes are put through verification.

The verifier exists basically to subvert or thwart any attempts to create or pass off a hostile .class file. Because classes are loaded over the network from a typically unknown source, the verifier is applied to them to make sure they conform to the contract between a .class file and the JVM specification. Another benefit of the verification step is that it speeds execution of the Java bytecodes at runtime. The speed is increased because the form is good, and the bytecodes don’t have to verify their own arguments at each execution. The verifier also checks the overall integrity of the .class file.

The verification process can be broken up into four phases. The first three are performed at class-load time, with the fourth performed by a subset of the actual Java bytecodes.

The first phase could be called the syntax check phase. It is responsible for ensuring the structural and syntactic integrity of the .class file being loaded. The following areas are examined during this phase:

• The magic number.
• The version number. Checked to be sure it is in sync with this VM implementation.
• Mandatory attributes. Checked to be sure they exist and are properly formed.
• The Constant pool. Verifies that only valid item types are contained.

The second phase is used to check the “semantic” consistency of the .class file. It is responsible for checking the following areas:

• The access flags. Checks that they are not being violated for the class, its fields, and its methods.
• The lineage of the object. Verifies the superclass field, for example.
• The constant pool items. Checks that these items are well-formed (for example, the Strings are strings, and so on).

The third phase is the most intense and is called the bytecode verifier. This phase performs a data-flow analysis on the actual bytecode stream that is contained in each method definition in the class. The following list represents the major features of the bytecode verifier, which ensures the following:

• The stack is in a consistent state for each bytecode encountered. That is, it verifies there is no under- or overflow of the expression stack.
• The arguments to the operands are in the appropriate domain.
• The types of values being put in or referenced from fields, arguments, and variables are correct for their usage.
• The arguments passed to method calls are of the right form.
• No field or variable is accessed without being properly initialized.

The final phase is actually performed at runtime and involves checks that could not be performed in phase three, as not all referenced classes are necessarily loaded in that phase. For each instruction that dynamically refers to another class (either a field or method), the linkage is examined. Then, the access permissions are checked. Furthermore, if all is OK, the referenced class is instantiated. Also, if the current bytecode references anything in the Constant Pool, it is resolved, and a special _quick variant of the bytecode instruction is replaced at that point in the bytecode stream. The _quick variants assume that the value required is directly accessible with no intermediate Constant Pool resolution requirement.

The JVM Bytecodes

This final section is a reference for the actual JVM bytecode instructions. There is not enough space in this section to include all of the details that are actually required to implement a JVM, but you should be able to write a simple bytecode disassembler with this information. The reference is in tabular format with the following columns:

• Instruction The literal mnemonic for this
  OpCode.
• OpCode The actual unsigned bytecode value.
• #Args The number of byte-sized operands in the bytecode stream that immediately follow the OpCode for this instruction.
• Description The basic semantics of this instruction.

When the JVM interpreter loop is running, there is actually one logical register that is used—the Program Counter, which represents the address in the bytecode stream of the currently executing instruction. Some of the instructions modify this Program Counter in order to alter the flow of execution. Otherwise, execution flows sequentially through the bytecode stream from instruction to instruction.

Table 36.1 Java Bytecode Instructions in OpCode Order

| Previous Chapter | Next Chapter |

|Table of Contents | Book Home Page |

| Que Home Page | Digital Bookshelf | Disclaimer |

To order books from QUE, call us at 800-716-0044 or 317-361-5400.

For comments or technical support for our books and software, select Talk to Us.

© 1996, QUE Corporation, an imprint of Macmillan Publishing USA, a Simon and Schuster Company