When troubleshooting bugs or performance problems while writing software programs, developers often need to trace these problems back to source code. Luckily, in the case of Java programs, there are several tools that can assist in this process by mapping program addresses to source code lines. However, the source code mapping that these tools provide is often imprecise because it doesn’t take into account inlined methods. This article explains why inlined methods raise challenges for source mapping and how the Java Virtual Machine can make inlining information visible to tools by passing it through the JVMTI layer. AMD Java Labs has implemented this technique, which we call JVMTI Event Piggybacking, in the Sun Hotspot JVM without changing the JVMTI specification.
The first three sections introduce the Java execution model and JVMTI. The next two sections discuss why inlining raises challenges for source mapping and different approaches one can take for tackling this problem. Next, we discuss our solution and its implementation in the Hotspot JVM. Finally, we give a high-level overview of how tools can use inlining information passed by the JVM to improve source mapping.
When we use the term “compilation” in the context of C and C++ programs, we often have in mind the process of compiling a source-level program directly into the machine code of the target architecture. However, Java has a different execution model than C and C++. Java programs are not compiled directly to machine code, but first to an intermediate representation called bytecode format. The program in bytecode format is then translated into native code and executed on the target architecture, using a variety of techniques such as interpretation, just-in-time compilation, and ahead-of-time compilation. The software layer that is responsible for this translation and execution of the program is the Java Virtual Machine (JVM).
Thus, in the Java world, the term “compilation” has two contexts. The first refers to the compilation of a source-level Java program into its bytecode equivalent. The second refers to the compilation of these bytecode instructions into machine instructions of the target architecture. It is this second meaning of “compilation” that we have in mind whenever we use the term in the rest of this article.
JVMs have a unique way of communicating with external tools such as profilers. The Java Virtual Machine Tools Interface (JVMTI) is a mechanism that allows the JVM to expose runtime information to such tools and provide these tools with a rich API that enables them to query this information and control the execution of the Java program. Profiling tools commonly use this interface to map program addresses to source code.
The basic unit of communication between the JVM and the external world is a JVMTI event. Each JVMTI event signals a specific phase in Java execution, such as the loading of a class or the compilation of a method. There are 39 different JVMTI events. These events are explained at:
http://java.sun.com/j2se/1.5.0/docs/guide/jvmti/jvmti.html#EventIndex
As you can see, these events cover a wide variety of phases in Java execution, such as the startup and initialization of the JVM, thread handling, class loading, method compilation, dynamic code generation, field accesses and modification, stack handling, exception handling, garbage collection, and thread synchronization.
Commercial JVMs such as Hotspot automatically generate these events at the proper execution phases. Tool writers can write JVMTI agents to listen for and respond to these events. A JVMTI agent is a program consisting of handler routines for each JVMTI event of interest.
A JVM will trigger a CompiledMethodLoad event immediately after it compiles a method to native code. A sample code follows to illustrate how one would write an agent that listens for CompiledMethodLoad events and prints the name of each method that was compiled.
Void JNICALL compiledMethodLoad (jvmtiEnv *jvmti_env, jmethodID method,
jint code_size, const void* code_addr, jint map_length, const jvmtiAddrLocationMap* map,
const void* compile_info) {
char* name = NULL;
char* signature = NULL;
char* generic_ptr = NULL;
if((*jvmti_env)->GetMethodName(jvmti_env, method, &name, &signature, &generic_ptr) == JVMTI_ERROR_NONE) {
fprintf(fp, “\nCompiled method load event\n”);
fprintf(fp, “Method name %s %s %s\n\n”, name, signature, generic_ptr);
}
}
The CompiledMethodLoad routine is the handler routine for CompiledMethodLoad events. The JVMTI interface provides similar handler routines for other events (e.g., ClassFileLoad, FieldAccess). A tool writer would implement the handler routines for the events that he is interested in. In this simple example, whenever there’s a CompiledMethodLoad event, we retrieve the name and signature of the method that was compiled, using the JVMTI callback GetMethodName, and print this information.
It is worth taking a closer look at the CompiledMethodLoad callback to understand each of its parameters. The first parameter, jvmti_env, is a pointer to the JVMTI environment. It is through this pointer that a tool has access to the rich API provided by the JVMTI spec. An example use of this pointer is:
((*jvmti_env)->GetMethodName(jvmti_env, method, &name, &signature, &generic_ptr)
This copies the name and signature of the method that was compiled into the variable’s name and signature.
The second parameter to the CompiledMethodLoad callback, method, is the ID of the method that was compiled. The third and fourth parameters, code_size and code_addr, give the size of the compiled code (in bytes) and its address in memory.
The fourth and fifth parameters, map_length and JVMTIAddrLocationMap, are related and deserve special mention. The JVMTIAddrLocationMap is a table that maps addresses in the compiled code to locations known in the JVMTI specification as jlocations. The JVMTI spec defines the format of a jlocation as:
typedef enum {
JVMTI_JLOCATION_JVMBCI = 1,
JVMTI_JLOCATION_MACHINEPC = 2,
JVMTI_JLOCATION_OTHER = 0
} jvmtiJlocationFormat;
That is, a jlocation could be a bytecode index, a machine code index, or something else depending on the JVM. You can find out what a jlocation means in the JVM that you’re using by calling the method:
jvmtiError
GetJLocationFormat(jvmtiEnv* env,
jvmtiJlocationFormat* format_ptr)
In the Sun Hotspot JVM, jlocations are indices into the bytecode representation of the program. As a result, the JVMTIAddrLocationMap is a table that maps compiled code addresses to bytecode indices.
This table provides a one-to-many mapping. Each entry in the JVMTIAddrLocationMap consists of a bytecode index and the starting address of the corresponding compiled code. The bytecode index is mapped to the address range beginning with this start address and ending before the start address of the compiled code corresponding to the next bytecode instruction.
The last parameter, compile_info, is a void pointer for JVMs to attach compilation information. It is described in the JVMTI spec as:
VM-specific compilation information. The referenced compile information is managed by the VM and must not depend on the agent for collection. A VM implementation defines the content and lifetime of the information.
The JVMTI spec leaves it open as to what information a JVM can pass through this pointer. We decided to use this pointer to pass method inlining information.
Although JVMTI provides rich information that can be used by performance analyzers, there are limitations in the JVM and the way the JVMTI spec has been interpreted. These limitations make it challenging for JVMs to provide tools with all the information they need to map program addresses precisely to source code.
One of these limitations has to do with inlined methods. When a method is compiled, the methods that it calls may be inlined into its own body. For example, consider the following code snippet:
int foo(int j)
{
return j+1;
}
public static void main(String[] args)
{
for(int i = 0; i < 3; i++)
{
j += foo(j);
}
}
Most JVMs are smart enough to see that the work being done inside the function foo is trivial (the incrementing of a counter); it would be less expensive to execute the code for foo as part of the code for main than to execute a separate procedure call to foo. As a result, most JVMs will inline the code for foo into the code generated for main.
How does all of this relate to our original problem of source mapping? Mapping addresses to source code is normally a two-step process. The first step is to map addresses to bytecode offsets, and the second step is to map bytecode offsets to source code line numbers. Most JVMs contain tables that perform these two levels of mapping. The first table, which maps addresses to bytecode offsets, would be returned in the CompiledMethodLoad callback as the JVMTIAddrLocationMap, in JVMs that support it. The second table, which maps bytecode offsets to source lines, can be accessed by calling the JVMTI API routine, GetLineNumberTable.
The problem is that, to provide accurate source mapping, the JVMTIAddrLocationMap would have to account for inlined methods. This means that compiled code addresses belonging to inlined methods would have to be mapped to bytecode offsets of the method that was inlined, not the original “outer” method. But JVMs are not required to implement the JVMTIAddrLocationMap in this way, so the accuracy of this two-step process of address-to-source mapping is not guaranteed.
How can the JVM communicate inlining information to tools for improved source mapping? The JVMTI spec does not define any events to indicate inlining, so one approach would be for the JVM to generate a separate CompiledMethodLoad event for every compiled method that has been inlined.
One problem with this solution is that frequent inlining can result in a proliferation of CompiledMethodLoad events, potentially degrading the performance of the JVM. Also, some optimizations may cause the code belonging to an inlined method to become scattered. To get around this, one could generate separate CompiledMethodLoad events for each address range belonging to an inlined method, but at the expense of increasing the total number of CompiledMethodLoad events.
Another problem is that CompiledMethodLoad events alone contain no inlining information. The only way to tell whether a particular event belongs to an inlined method would be to compare the address ranges returned in the event callback with those of other CompiledMethodLoad events that have been generated so far. This requires additional bookkeeping. A JVMTI agent would have to maintain a list of CompiledMethodLoad events, and update this list whenever methods are recompiled or unloaded.
An easy-to-implement solution that avoids the above problems is to attach inlining information to the CompiledMethodLoad callback. Recall the function prototype for this callback:
Void JNICALL compiledMethodLoad (jvmtiEnv *jvmti_env, jmethodID method, jint code_size,
const void* code_addr, jint map_length, const jvmtiAddrLocationMap* map, const void* compile_info) {
char* name = NULL;
char* signature = NULL;
char* generic_ptr = NULL;
if((*jvmti_env)->GetMethodName(jvmti_env, method, &name, &signature, &generic_ptr) == JVMTI_ERROR_NONE) {
fprintf(fp, “\nCompiled method load event\n”);
fprintf(fp, “Method name %s %s %s\n\n”, name, signature, generic_ptr);
}
}
According to the JVMTI spec, the void pointer compile_info exists to allow JVMs to pass compilation information. However, JVMs that don’t use this pointer can be modified to attach inlining information to it. One of these JVMs is Sun Hotspot, so we chose this JVM for our implementation.
For every compiled method, Hotspot maintains a list of data structures called PC Descriptors. Each PC Descriptor tells you what method invocations are on the compile-time stack at each program counter offset. This indirectly gives you inlining information. Methods that are on the compile-time stack at a particular PC address but aren’t explicitly called at that code location have been inlined at that PC address.
When running the Hotspot JVM in debug mode, you can view these PC Descriptors by enabling the command line option –XX:+PrintNMethods.
As an example, consider this program:
public class Main{
public final int fillarray(int[][] _grid, int _width, int _height, int _value){
for (int x=0; x<_width; x++){
for (int y=0; y<_height; y++){
_grid[x][y]=_value + inlinedhelper(_grid, _width, _height);
}
}
return inlinedhelper(_grid, _width, _height);
}
public final int inlinedhelper(int[][] _grid, int _width, int _height)
{
int total = 0;
for (int x=0; x<_width; x++)
{
for (int y=0; y<_height; y++)
{
total+=_grid[x][y];
}
}
System.out.println(0x1234);
System.out.println(0x1397);
System.out.println(0x3645);
return total;
}
public static void main(String[] _args){
int width=100;
int height=100;
int[][] grid = new int[width][height];
Main main = new Main();
long startNanoTime = System.nanoTime();
for (int i=0; i<10; i++){
main.fillarray(grid, width, height, 0);
}
long endNanoTime = System.nanoTime();
}
}
Figure 1: Sample program illustrating inlining.
The main method calls a method fillarray ten times. This method fills up a two-dimensional array by calling another method, inlinedhelper. The method inlinedhelper, which accesses the array, is actually called a total of 100*100*10 = 100,000 times. Because it is a frequently executed method, a JVM is likely to inline it into the body of the method fillarray. Using a profiling tool, one can verify that inlinedhelper is being inlined into fillarray.
If you run the program in Figure 1 inside the debug version of the Sun Hotspot JVM, enabling the –XX:+PrintNMethods option, one of the sections you will see in the output will look like the following:
pc-bytecode offsets:
PcDesc (pc=0x1a offset=1a2cfda)
LMain;::fillarray ([[IIII)I (null) @-1
PcDesc(pc=0x2a offset=1a2cfea):
LMain;::fillarray ([[IIII)I (null) @6
PcDesc(pc=0x30 offset=1a2cff0):
LMain;::fillarray ([[IIII)I (null) @21
PcDesc(pc=0x3c offset=1a2cffc):
LMain;::fillarray ([[IIII)I (null) @15
PcDesc(pc=0x42 offset=1a2d002):
LMain;::fillarray ([[IIII)I (null) @18
PcDesc(pc=0x68 offset=1a2d028):
LMain;::fillarray ([[IIII)I (null) @21
PcDesc(pc=0x72 offset=1a2d032):
LMain;::inlinedhelper ([[III)I (null) @26
LMain;::fillarray ([[IIII)I (null) @30
PcDesc(pc=0x74 offset=1a2d034):
LMain;::inlinedhelper ([[III)I (null) @21
LMain;::fillarray ([[IIII)I (null) @30
PcDesc(pc=0x81 offset=1a2d041):
LMain;::inlinedhelper ([[III)I (null) @26
LMain;::fillarray ([[IIII)I (null) @30
Figure 2: PC Descriptors displayed by the –XX:+PrintNMethods Debug Option
These are the PC Descriptors for the method Main.fillarray. This output shows that, at the PC addresses 0x1a-0x68, fillarray is the only method on the compile-time stack. This is because it hasn’t yet called any other method. However, starting at offset 0x72, inlinedhelper is also on the stack. This is the point in the code at which inlinedhelper is being invoked by fillarray. The values after the@ signs are bytecode offsets.
We extended the Hotspot JVM so that, for every compiled method, it initializes the void pointer of the CompiledMethodLoad callback with the entire compile time stack for that method; this includes all of the PC Descriptor information. The format of the information passed through the void pointer is:
//Record that contains information about method activations on the compile-time stack at a particular pc address.
typedef struct InlineInfoRecord_s {
void* pc;
void* offset;
jmethodID* stackframes;
jint* bytecodeindexes;
jint numstackframes;
jint type;
struct InlineInfoRecord_s* next;
}InlineInfoRecord;
The field pc is the PC address in question. The field stackframes is an array of method IDs that tells you what methods are on the compile-time stack at that PC address. The field bytecodeindexes is a table that maps these method IDs to bytecode indexes. This tells you, for each method on the compile-time stack, which bytecode of the method is being executed at that PC address. The field numstackframes tells you how many method activations are on the compile-time stack. This field allows you to quickly check whether inlining is happening. If the value of this field is greater than one, then inlining is occurring at that PC address.
Although we use the void pointer to pass inlining information, nothing prevents us from using it to pass other kinds of information, such as information about register allocation, garbage collection, or optimization decisions. One way to pass different types of information would be to attach different types of records (e.g., InlineInfoRecord, OptimizationInfoRecord, etc.) to the same list. To allow for this flexibility, each record also has a field called type, which identifies the type of the record.
Our main change to the Hotspot JVM was to the post_compiled_method_load routine, which is defined in JVMTIExport.cpp. This routine is called as soon as a method is compiled. We modified it to retrieve the list of PC Descriptors for the compiled method and pass this information to the void pointer before sending the CompiledMethodLoad event.
void JvmtiExport::post_compiled_method_load(nmethod *nm) {
JavaThread* thread = JavaThread::current();
JvmtiCompiledMethodLoadEventMark jem(thread, nm);
PCDescriptorList pclist;
//Get the list of inlining information records for this nmethod
nm->get_pc_descriptors(&pclist);
//Pass this inlining information into the void pointer.
jem.set_void_pointer(pclist.getList());
JvmtiJavaThreadEventTransition jet(thread);
jvmtiEventCompiledMethodLoad callback = env->callbacks()->CompiledMethodLoad;
if (callback != NULL) {
//Send the compiled method load event. Note the void pointer compile_info being passed as the last parameter.
(*callback)(env->jvmti_external(), jem.jni_methodID(),
jem.code_size(), jem.code_data(), jem.map_length(),
jem.map(), jem.compile_info());
}
}
Figure 3. Code sample from post_compiled_method_load routine.
As an example of how this information can be used by tools, a small JVMTI agent that accesses the CompiledMethodLoad void pointer and prints the list of PC Descriptors follows.
void JNICALL compiledMethodLoad (jvmtiEnv *jvmti_env, jmethodID method, jint code_size, const void* code_addr,
jint map_length, const jvmtiAddrLocationMap* map, const void* compile_info) {
char* name = NULL;
char* signature = NULL;
char* generic_ptr = NULL;
InlineRecordList* pcs;
if((*jvmti_env)->GetMethodName(jvmti_env, method, &name, &signature, &generic_ptr) == JVMTI_ERROR_NONE) {
fprintf(fp, "\nCompiled method load event\n");
fprintf(fp, "Method name %s %s %s\n\n", name, signature, generic_ptr);
//Here the agent is accessing the void pointer and casting it to a list of inlining information records
pcs = (InlineRecordList *)compile_info;
if(pcs != NULL) {
/*This is where the inlining information in the void pointer gets used. The agent prints each of the inline information records */
printPCDescriptors(pcs, jvmti_env, fp);
Figure 4. JVMTI agent that uses inlining information piggybacked onto the CompiledMethodLoad callback.
Figure 5 is sample output when we run this agent on our example program, using the modified Hotspot JVM:
Compiled method load event
Method name fillarray ([[IIII)I (null)
Printing PC Descriptors
PcDescriptor(pc=0x1a offset=1a2cfda):
LMain;::fillarray ([[IIII)I (null) @-1
PcDescriptor(pc=0x2a offset=1a2cfea):
LMain;::fillarray ([[IIII)I (null) @6
PcDescriptor(pc=0x30 offset=1a2cff0):
LMain;::fillarray ([[IIII)I (null) @21
PcDescriptor(pc=0x3c offset=1a2cffc):
LMain;::fillarray ([[IIII)I (null) @15
PcDescriptor(pc=0x42 offset=1a2d002):
LMain;::fillarray ([[IIII)I (null) @18
PcDescriptor(pc=0x68 offset=1a2d028):
LMain;::fillarray ([[IIII)I (null) @21
PcDescriptor(pc=0x72 offset=1a2d032):
LMain;::inlinedhelper ([[III)I (null) @26
LMain;::fillarray ([[IIII)I (null) @30
PcDescriptor(pc=0x74 offset=1a2d034):
LMain;::inlinedhelper ([[III)I (null) @21
LMain;::fillarray ([[IIII)I (null) @30
PcDescriptor(pc=0x81 offset=1a2d041):
LMain;::inlinedhelper ([[III)I (null) @26
LMain;::fillarray ([[IIII)I (null) @30
Figure 5: Sample output from JVMTI agent in Figure 4.
Notice that inlinedhelper is being inlined into fillarray from the PC address 0x72 onwards, and that all of the addresses match those in the –XX:+PrintNMethods option. This shows that the inlining information provided by the void pointer mechanism is accurate.
Here’s an example of how a JVMTI agent would use this information to improve source mapping. Recall the format of the CompiledMethodLoad callback:
Void JNICALL compiledMethodLoad (jvmtiEnv *jvmti_env, jmethodID method, jint code_size,
const void* code_addr, jint map_length,
const jvmtiAddrLocationMap* map, const void* compile_info)
When an agent receives a CompiledMethodLoad event, it knows the address ranges of the compiled code in question. (This is given by the code_size and code_addr.) It is also given by the list of inline information records in the void pointer compile_info.
For each PC address, the agent accesses the void pointer to retrieve the inline information record for that address. Recall the format of an inline information record:
//Record that contains information about method activations on the compile-time stack at a particular pc address.
typedef struct InlineInfoRecord_s {
void* pc; //the pc address
void* offset;
jmethodID* stackframes; //list of method ids on the compile time stack
jint* bytecodeindexes; //mapping between method ids and bytecode indices
jint numstackframes; //Number of method activations on the compile-time stack
jint type;
struct InlineInfoRecord_s* next;
}InlineInfoRecord;
The agent checks the field numstackframes. If the number of stack frames is greater than one, then inlining is occurring at that PC address. The agent accesses the array stackframes to retrieve the method ID of the topmost method on the compile time stack at that PC address:
jmethodID topmethod = stackframes[0]
The bytecode index that is being executed at that PC address is:
jint bcindex = bytecodeindexes[0].
The agent can now retrieve the table that maps bytecodes to source code line numbers by calling the JVMTI API routine, GetLineNumberTable:
jvmtiLineNumberEntry * lineTable = NULL;
jint lineTableLen = 0;
(*jvmti_env)->GetLineNumberTable(jvmti_env, topmethod, &lineTableLen, &lineTable);
The line number table will be returned in the pointer lineTable. Given this table and the bytecode index, it is straightforward to access the source line number of the inlined method. This is given by:
lineTable[bcindex].linenumber
The agent finally maps this source line to the PC address in question. It now has sufficient information to display program addresses and source code side by side.
We have illustrated a mechanism by which JVMs can piggyback additional information onto the CompiledMethodLoad JVMTI event, making this information visible to external tools. An advantage of this mechanism is that it doesn’t alter the JVMTI spec and is reusable for passing arbitrary information, such as register allocation data or information about optimization decisions. So, although the short-term benefits are for Java analysis tools that more accurately map program addresses to source code, this mechanism has great potential for more widespread applications.
To comment on this article in our blogs, and for more information about the work being done by AMD Java Labs, visit the Java Zone on AMD Developer Central.
Vasanth Venkatachalam received his Masters degree in computer science in 2002 and his PhD degree in computer science in 2007 from the University of California, Irvine. Since July 2007, he has been working as a software engineer at Advanced Micro Devices, Inc., in Austin, TX. As a member of the AMD Java Labs team, he focuses on JVM performance optimizations, Java development, and the development of tools for efficient and accurate performance analysis.