Browse Prior Art Database

Fast Identification Of Previously Retrieved Callstacks Disclosure Number: IPCOM000200962D
Publication Date: 2010-Nov-01
Document File: 2 page(s) / 20K

Publishing Venue

The Prior Art Database


Disclosed is a system for associating a unique identifier for every call stack within Java*. The method uses a reversible algorithm within the Java Virtual Machine along with appending the call depth to the identifier and maintaining confidence statistics.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 01 of 2

Fast Identification Of Previously Retrieved Callstacks

It generally takes a long time for agents to retrieve call stacks from Java*. There is a need for a fast method to identify call stacks that have already been retrieved.

The disclosure involves associating a unique identifier (id)

adding a new extended Java Virtual Machine Tool Interface (JVM TI) function to the Java Virtual Machine(JVM)

which returns this id, the agent can first query the id, then

only retrieve the entire call stack if it has not been seen before. Since the agent may represent the call stacks as nodes in a call tree, the IDs associated with the call stacks can be put into a hash table that contains the pointers to the appropriate nodes in the call tree.

As the agent associates IDs with more and more call stacks, the agent will

execute faster and faster.

However, this ideal implementation may not be practical because the JVM may be unable to maintain a table of all previously reported call stacks. Thus, it may not know if it has already reported a given call stack and cannot guarantee that a call stack ID is unique.

A benefit of the disclosure is the generation of a usable ID with minimal impact

As the JVM executes its methods, for each thread, the JVM must always know which

method it is executing and the call depth. It is possible to generate a reversible ID based on these two numbers. The ID is reversible if the programmer can regenerate the previous ID by reversing the operation performed when the call was made.

For example, assume that A and B are methods,

                                            0xAA and 0xBB, respectively. Further assume that A is already at call depth N and the current call stack ID is 0x77. The simplest reversible algorithm is XOR (exclusive-or). If A calls B, then the ID of the call stack at depth N+1 is 0x77 XOR 0xBB = 0xCC. It is reversible because 0x77 returns when B returns to A by simply repeating the computation. That is, 0xCC XOR 0xBB = 0x77. Programmers could even compute the ID of the call stack

when A returns to its caller at depth N-1 as 0x77 XOR 0xAA = 0xDD.

Thus, by using this reversible algorithm, the system could traverse up and down the call stack as the application executes. It would only need the current ID and the ID of the method it is calling or leaving to generate the new ID. Each time the system returns to the same point in the call stack, the ID is the same.

The advantage of this approach is the extremely low amount of state memory that must be retained. However, using XOR with the method ID may not be sufficient because it is possible to generate the same ID for different call stacks. In fact, recursive methods

would repeat the same ID every two levels of nesting where only the method ID is used.

To address this problem, the system may use the c...