Browse Prior Art Database

Method for fast-stack crawling within a 64-bit architecture

IP.com Disclosure Number: IPCOM000007988D
Publication Date: 2002-May-09
Document File: 2 page(s) / 28K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for fast-stack crawling within a 64-bit architecture. Benefits include improved performance.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 50% of the total text.

Method for fast-stack crawling within a 64-bit architecture

Disclosed is a method for fast-stack crawling within a 64-bit architecture. Benefits include improved performance.

Background

              Modern managed runtimes (such as Java virtual machines and CLI execution environments) require an efficient mechanism for inspecting the runtime stack of activation records. This mechanism is known as stack crawling.

              Stack crawling is necessary for implementing several important language features such as garbage collection, security, and exception processing. Stack crawling is also required for dynamic call chain profiling. To crawl the stack, the runtime needs a mechanism that maps a call site's address to the descriptor containing the call site (the caller).

              Conventional techniques for stack unwinding require the compiler to register the address range(s) comprising a method (function) with the managed runtime. The managed runtime maintains a data structure that maps instruction ranges to method descriptors. This data structure is typically a binary search tree or a hash table. To map a call site address to a method descriptor, the runtime VM looks up the call site address in this data structure.

              A method's (function’s) descriptor contains information, such as the activation record size, security object, and exception handlers. This information is used by the runtime VM to perform the following tasks:

§         Enumerate the method's root object references for garbage collection

§         Identify the method's security privileges for the runtime security manager

§         Find exception handlers for the method

§         Unwind to the method caller's activation record on the stack

General description

              The disclosed method describes an efficient stack crawling mechanism for a 64-bit architecture.

Advantages

              The mechanism described in the disclosed method is more efficient than conventional practice because the runtime table that maps a method index to a method descriptor can be accessed and updated in realtime. The time complexity of accessing or updating a binary tree is O(lg n). A hash table cannot guarantee realtime accesses or updates.

Detailed description

              The disclosed method uses a no-operation (no-op) instruction to efficiently map the address of a call site to the caller's descriptor. Each method is assigned a unique method index. A runtime table maps a method's index to its descriptor. The runtime compiler as...