Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-02-26
2001-11-13
Powell, Mark R. (Department: 2762)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06317870
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is generally related to computer programs and, more particularly, is related to a system and method for efficiently sharing code, specifically, generating software intermodule procedure calls.
2. Description of Related Art
As is known in the computer and software arts, an executable file is typically composed of several separately compiled object modules and libraries. In the past, all of the code necessary to build an executable file was usually linked into one monolithic file. Nowadays, it is more likely that an executable file generated by a compiler and linker will be incomplete, requiring a plurality of shared libraries (or dynamically linked libraries, in OS/2 and Windows parlance). The base executable program is linked together with any dependent shared libraries at load time to produce a complete program.
There are many advantages to the foregoing configuration and technique. In particular, common functionality, such as the standard input/output [I/O] facilities of the C language, for example, can be shared among all of the processes running on the system, rather than requiring that each have its own private copy. When a patch or bug fix is required for a routine within a shared library, the vendor can ship a new library, and all of the programs that depend on the library will automatically pick up the new code the next time they are executed, without the need for recompilation.
Unfortunately, the code sharing configuration and technique comes at the price of a performance penalty. Functions within a load module (the base image for a particular program or any shared library) can use efficient calling sequences when invoking other functions within the same load module, because the complete physical layout of the module is known at link time. Typically, the calling sequence involves a program counter relative branch from the calling function to the destination. However, calls between dynamically linked modules use more time consuming calling sequences, because the relative placement of the calling module and the called module are not known until runtime. In some embodiments, there is also an additional large performance penalty to modify code for all inter-module calls when the program is loaded.
One solution to this performance penalty problem is to introduce the notion of an import stub. Suppose that a function F in module A calls a function G in module B. The code for function F is compiled as if the code for function G is in the same module, and the displacement of the called function G in module B is left for the linker to fix up. When the linker discovers that the called function G in module B is not in the same module A, the linker creates an import stub for the called function G in module B in the calling module's module A. While there may be many calls to function G in module B from different locations in module A, all of the calls are fixed up to pass control to the same import stub. Then, at load time, only the import stubs code has to be modified.
There should be as many import stubs as the number of external functions referenced from within the module. In general, this will be less than the total number of calls to external functions, so the amount of work required at load time is reduced.
A further improvement is to have the import stub perform the symbol table lookup the first time it is invoked (i.e., “bind-on-reference”). This improvement reduces the load time overhead to zero, but it involves somewhat more work the first time the import stub is executed. The problem with this technique is that every inter-module function call has to pass control through an import stub which introduces extra overhead vis-à-vis intra-module function calls.
Heretofore, software developers have lacked a system and method for accomplishing code sharing, particularly, inter-module function calls, in an more efficient way.
SUMMARY OF THE INVENTION
The present invention provides a system and method for efficient intermodule procedure calls. Briefly described, in architecture, the system can be implemented as follows. The system provides for a program linker to translate a non-executable program into the computer program. The program linker also creates an import stub when the program linker encounters a call instruction to an unresolved module in the computer program. The program linker further modifies the call instruction to the unresolved module to be a call instruction to the created import stub. The import stub determines a location of the unresolved module a first time the unresolved module is called. The import stub then modifies the call instruction to the unresolved module the first time the unresolved module is called to be a direct call the unresolved module at the location determined after the first time the unresolved module is called.
The present invention can also be viewed as providing a method for efficient code sharing. In this regard, the method can be broadly summarized by the following steps: The import stub just passes control to the external function. It is an added call in between the caller and the callee when the two are in separate load modules. The import stub knows the location of the caller and the location of the callee, so that whenever the import stub is executed, the import stub can dynamically patch the caller to pass control directly to the callee in the future. Although that particular caller will never go through the import stub again, there may be other callers within the same load module that will. Each call site will be patched, or modified, to transfer control directly to the external target the first time that it passes control through the import stub.
The present invention has numerous advantages, a few of which are delineated hereafter as merely examples.
An advantage of the invention is that call sites which are never executed will not be patched in order to reduce program execution time. In the worst case, each call site will be executed one or more times, and the patching overhead will be just as high as it would have been for the loader to fix up each and every call site at load time. The difference is that the expense is incurred incrementally, which is generally more acceptable to the user of the program than incurring all of the expense at load time. Also, this is the worst case expense. In typical program execution, many call sites to external targets will never be executed, and in accordance with this invention, they will not be patched to reduce program execution time.
Another advantage of the present invention is that it is simple in design, and efficient in operation.
Another advantage of the present invention is that every invocation of a modified call instruction will be more efficient than going through an import stub. Thus, call sites which are visited many times during program execution will exhibit a performance improvement.
Other features and advantages of the present invention will become apparent to one with skill in the art upon examination of the following drawings and detailed description. It is intended that all such additional features and advantages be included herein within the scope of the present invention.
REFERENCES:
patent: 6026235 (2000-02-01), Shayghnessy
patent: 6154878 (2000-11-01), Saboff
Hewlett--Packard Company
Holmes Michael B.
Powell Mark R.
LandOfFree
System and method for optimization of inter-module procedure... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for optimization of inter-module procedure..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for optimization of inter-module procedure... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2616625