Electrical computers and digital processing systems: processing – Architecture based instruction processing – Stack based computer
Reexamination Certificate
2001-10-09
2004-09-21
Lane, Jack A. (Department: 2186)
Electrical computers and digital processing systems: processing
Architecture based instruction processing
Stack based computer
Reexamination Certificate
active
06795910
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention generally relates to computer systems. More particularly, and not by way of any limitation, the present invention is directed to a system and method for managing stack utilization in a high performance multiprocessing environment.
2. Description of Related Art
The use of stackts in association with program execution in computing eviroments is well known: stacks are initialized, contents are pushed or pulled based on calls to and returns from sub-functions, subroutines, etc., and the programs are executed to completion. There is no automatic way, however, to determine the required depth of a stack before a program is launched. Accordingly, it becomes necessary to ensure that there is no conflicting use of stack space due to, e.g., stack overflow, which can otherwise lead to stack corruption.
Two solutions are currently available. In one existing arrangement, the user is required to inspect the program code manually and place debug statements in the code to ensure that the stacks growing towards each other (for example, a stack area initialized for the program, which grows in one direction, and its associated register spill area set up by the operating system, which grows in the opposite direction) do not use the same memory. Another solution is to fill stack memory with markers having specific bit patterns. The code is executed in normal fashion and, after the execution is complete, the user needs to verify that the markers still exist.
While these solutions are generally useful, they are nevertheless beset with several shortcomings and disadvantages. First, forcing the user to step through the code manually is extremely inconvenient and imposes severe performance-related constraints. On the other hand, embedding marker patterns at arbitrary locations in a stack area is not a highly reliable mechanism for detecting stack overflow. For example, even if the marker pattern remained after executing the program, it is no guarantee that there was no stack overflow because the instruction(s) overwriting the marker area might have written a pattern that is identical to the marker pattern. Also, there may be situations where stack overflow does not actually overwrite the marker location. Rather, the overflow may simply “skip” the marker area in the stack, which makes it very difficult to diagnose a corrupted stack. Further, where two-stack arrangements are implemented, each stack growing towards the other, there is the additional problem of not being able to identify which of the two stacks actually caused the overflow.
Additionally, regardless of whether one-stack or two-stack arrangements are utilized, the conventional stack utilization management schemes are woefully inadequate with respect to detecting stack conditions that are either invalid or have the potential to become so. For instance, where stack pointer operations are involved, the current techniques do not test whether a new location to which the stack pointer is to be moved may violate a predetermined stack range. Also, because only write operations that affect the marker's bit pattern are detectable, invalid conditions arising out of read operations cannot be discovered in the present schemes.
SUMMARY OF THE INVENTION
Accordingly, the present invention advantageously provides a system and method for managing stack utilization with particular reference to two-stack arrangements in a high performance computing environment such as, for example, architectural simulators for multiprocessor (MP) platforms, specific hardware implementations having known or heretofore unknown computer architectures, and the like, that overcomes these and other aforementioned deficiencies of the state-of-the-art solutions. Preferably, the two stacks of an exemplary stack arrangement are provided to be operable to grow towards each other. An application programming interface (API) is provided for facilitating user interaction with a stack management system associated with the computing environment, whereby each of the two stacks is initialized with respect to a stack base, a growth direction indicator and a stack pointer. High water marks are maintained for tracking each stack pointer's farthest location from the respective stack base during the execution of a program. When a program instruction is operable to access a location in either of the stacks, one or more validity rules are applied to determine if the access operation is permissible. Where the program instruction is operable to modify either of the stack pointers, another set of validity rules are applied to determine if the stack pointer operation is permissible. User warning and optional return of program control are available when an invalid access operation or stack pointer operation is attempted.
In one aspect, the present invention is directed to a method for managing utilization of a two-stack arrangement. Upon fetching a program instruction to be executed in a computing environment, a determination is made whether the program instruction requires or involves accessing a location in either of the stacks, which are operable to grow towards each other. If so, a further determination is made whether the location to be accessed is within a predetermined valid stack range of either the downward-growing stack or the upward-growing stack. Preferably, the valid stack range for a stack is defined as the stack area bounded between the stack base and the current location of its valid stack pointer. In one exemplary mode of operation, a user warning is provided upon determining that the location to be accessed is not within the predetermined valid stack range specified with respect to the downward-growing stack or, alternatively, within the predetermined valid stack range specified with respect to the upward-growing stack. In addition to providing a suitable warning, control may be returned to the user or a suitable interrupt handler in a further exemplary mode of operation.
In another exemplary embodiment of the present invention, the methodology for managing stack utilization is operable to verify whether a stack pointer operation in a two-stack arrangement is capable of giving rise to stack overflow. The stacks are operable to grow towards each other and each stack is preferably initialized with a stack base, a direction indicator and a stack pointer. Also, a high water mark is initialized for each stack in order to track the stack pointer's location during execution of a program in a computing environment. Preferably, the high water marks operate to identify each stack pointer's farthest location from the stack base associated therewith that was attained in a program run. Upon fetching a program instruction to be executed in the computing environment, a determination is made if the program instruction is operable to modify either of the stack pointers' current location to a new location. If so, a further determination is made whether either of the new locations violates a predetermined condition with respect to the two-stack arrangement. A user warning and/or optional return of control may be provided when either of the new locations violates one of the predetermined conditions, e.g., the new location is out of range, the new location of one stack pointer crosses over the current location of the other stack pointer, or the new location of one stack pointer crosses over the high water mark of the other stack pointer.
In another aspect, the present invention is directed to a system for managing utilization of a two-stack arrangement. A interfacing structure is provided in conjunction with an architectural simulator or actual hardware platform to initialize a stack base, a stack pointer and a direction indicator for each stack. A high water mark is also initialized for each of the stacks, which are operable to grow towards each other. A software or hardware structure is provided for determining if a program instruction requires accessing a location or modifying the current stack poin
Bolding Joe
Everett Gerald
Tormey Dan
Hewlett--Packard Development Company, L.P.
Lane Jack A.
LandOfFree
Stack utilization management system and method for a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Stack utilization management system and method for a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stack utilization management system and method for a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3189167