Electrical computers and digital processing systems: processing – Architecture based instruction processing – Stack based computer
Reexamination Certificate
2001-10-09
2004-11-30
Lane, Jack (Department: 2188)
Electrical computers and digital processing systems: processing
Architecture based instruction processing
Stack based computer
Reexamination Certificate
active
06826675
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 stacks in association with program execution in computing environments 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
In one embodiment, a system and method is disclosed for managing stack utilization with particular reference to single-stack arrangements in a 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. An application programming interface (API) is provided for facilitating user interaction with a stack management system associated with the computing environment, whereby an exemplary unidirectional single stack is initialized with respect to a fixed stack marker boundary, a stack base and a stack pointer. A high water mark is maintained for tracking the stack pointer's farthest location from the stack base attained during the execution of a program. When a program instruction is operable to access a stack location, one or more validity rules are applied to determine if the access operation is permissible. Where the program instruction is operable to modify the stack pointer, 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 unidirectional stack. 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 the unidirectional stack. If so, a further determination is made whether the location to be accessed is within a predetermined valid stack range (e.g., the stack area bounded by the stack base and the current location of a valid stack pointer associated therewith). 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 stack base of the stack. In another exemplary mode of operation, control may be returned to the user or a suitable interrupt handler.
In another exemplary embodiment of the present invention, the methodology for managing stack utilization is operable to verify whether a stack pointer operation is capable of giving rise to stack overflow. The unidirectional stack is preferably initialized with a fixed stack marker, a stack base and a stack pointer. Also, a high water mark is initialized for tracking the stack pointer's location during execution of a program in a computing environment. Upon fetching a program instruction to be executed in the computing environment, a determination is made if the program instruction is operable to modify the stack pointer's current location to a new location in the unidirectional stack. If so, a further determination is made whether the new location is within a predetermined stack range (e.g., comprising a region bounded by the stack base and stack marker). If the location is not within the predetermined stack range, a suitable warning may be provided. Optionally, control may be returned to the user or an interrupt handler.
In another aspect, the present invention is directed to a system for managing utilization of a unidirectional stack. A interfacing structure is provided in conjunction with an architectural simulator or actual hardware platform to initialize a fixed stack marker and a stack base for the unidirectional stack in the computing environment. A software or hardware structure is provided for determining if a program instruction requires accessing a location or modifying the current stack pointer's location in the unidirectional stack. Warning means are available for providing a warning upon determining that the location to be accessed or the stack pointer's new location is not within a valid stack range. Optionally, the stack utilization management system may include appropriate interrupt handlers when control is returned upon determining that the validity conditions are not satisfied.
REFERENCES:
patent: 5903899 (1999-05-01), Steele, Jr.
patent: 6449625 (2002-09-01), Wang
Bolding Joe
Everett Gerald
Tormey Dan
Hewlett--Packard Development Company, L.P.
Lane Jack
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-3322242