Intelligent processing of external object references for dynamic linking

Performance information can be utilized for comparison of resolving an external object reference through a linking module against accessing the external object directly (“relocation processing”). With the performance information, a determination of whether performing relocation processing on a runtime linked external object reference provides improved runtime performance sufficient to outweigh the runtime linking overhead incurred from the relocation processing is made. If the improvement in runtime performance is sufficient, then the runtime linked external object reference, or the code section that includes the reference, is marked to indicate that relocation processing should be applied.

BACKGROUND

1. Field of the Invention

The present invention relates to the field of computers. More specifically, the present invention relates to optimization.

2. Description of the Related Art

Executable files may include external object references to be linked at runtime. Some files or objects that are linked at runtime instead of during compile time include dynamically linked libraries, shared objects, and relocatable modules. The runtime linked objects are maintained separately from executable files that reference the runtime linked objects. A runtime linker/loader, embodied within an executable file or operating environment, finds runtime linked objects that are referenced in the executable file and loads the objects into execution space.

A link-editor can provide facilities for keeping segments that include external object references read-only. Keeping these segments as read-only causes each cross-module call or external data reference to be done through an extra redirection, such as a table, followed by a loading of the object's address. Keeping code segments as read-only code segments and calling external objects with redirection (or indirection) introduces application runtime overhead for external object function calls and external data references. Instead of calling external objects with redirection, the reference to the external object may be resolved directly (“relocation processing”). However, relocation processing introduces runtime linking overhead that may outweigh the redirection overhead. Accordingly, a technique is desired that intelligently processes external object references of a code unit to be resolved either directly or indirectly.

SUMMARY OF THE INVENTION

It has been discovered that performance information can be utilized for comparison of resolving an external object reference through a linking module against accessing the external object directly (“relocation processing”). The comparison allows determination of the more beneficial avenue for processing a runtime linked external object reference. Selectively indicating whether a runtime linked external object reference should be modified or not modified based at least in part on performance information provides improved application performance that outweighs additional runtime linking overhead incurred from relocation processing.

The determination can be based at least in part on a comparison realized with an inequality that reflects the relationship between increased runtime linking overhead and optimized runtime performance. Accordingly, runtime linked external object references are indicated as modifiable if relocation processing is determined to be more efficient.

These and other aspects of the described invention will be better described with reference to the Description of the Preferred Embodiment(s) and accompanying Figures.

DESCRIPTION OF THE PREFERRED REALIZATION(S)

The description that follows includes exemplary systems, methods, techniques, instruction sequences and computer program products that embody techniques of the present invention. However, it is understood that the described invention may be practiced without these specific details. In other instances, well-known protocols, structures and techniques have not been shown in detail in order not to obscure the invention.

FIGS. 1A-1Bdepict modification of code to improve application performance according to some realizations of the invention.FIG. 1Adepicts an optimization tool marking sections of a code unit for modification according to some realizations of the invention. A code unit101has been translated (i.e., target code, such as machine level code). The code unit101includes external object references for runtime linking. These external object references may be references to shared libraries, plug-in code units, drivers, etc. Performance information103(e.g., profile data for the code unit101, optimization heuristics, etc.) corresponds to the code unit101. Although the performance information103is depicted separate from the code unit101, the performance information103may be embedded in the code unit101. An optimization tool105retrieves the performance information103(perhaps some of the performance information103if it includes performance information for additional code units) that corresponds to the dynamic runtime linked external object references of the code unit101.

The retrieved performance information includes one or more of execution frequency, execution time, load time, link time, etc. The performance information may correspond directly with an external object reference, with a sequence of instructions in the code unit101that include the external object reference, etc.

The optimization tool105determines the efficiency of modifying each of the runtime linked external object references of the code unit101according to the retrieved performance information. For example, assume T_res has been determined to be the time to perform relocation processing for an external object reference (e.g., an external function call, external data reference, etc.). Also assume that T_del has been determined to be the estimated improved execution time, according to retrieved performance information, for the one time execution of the relocated external object reference. For example, assume a code sequence executes within tiseconds. After relocation processing optimization, assume the same code sequence executes in t2seconds, t2<t1. The estimated improvement in runtime of the code sequence is t1−t2=T_del. Finally, N is the number of times that the sequence of instructions that include the external object reference are expected to be executed during runtime. If T_res<T_del*N, then runtime relocation processing should be introduced to optimize the external object reference.

For those external object references that can be modified to improve the code unit's runtime without significantly increasing runtime linking overhead, the optimization tool105marks those external object references to indicate that they should be modified during runtime linking (“runtime linking optimization candidate external object reference”). Markings are indicated inFIG. 1Awith darkened blocks in the code unit101. Various techniques can be employed to mark code units. For example, relocation entries are created in an ELF file (e.g., in a .rela.text section), and a .dynamic section of the ELF file is modified to indicate runtime relocation against the text section. In realizations of the invention, sequences of instructions (“code section”) that include one or more runtime linking optimization candidate external object references are marked (e.g., a loop, a sub-routine call, etc.). Various realizations of the invention may factor in additional criteria that may prevent a runtime linking optimization candidate external object reference from being optimized. For example, in the case of a 64-bit PLT call optimization, scratch registers may be used in the optimized sequence of instructions. If the call's delay slot instruction uses one of these scratch registers, then runtime relocation processing may not be introduced.

Various techniques are implemented in realizations of the invention to “mark” the code unit. For example, a sequence of instructions that includes one or more candidate external object references may be explicitly marked as modifiable or unmodifiable. The default may be for all of the code to be unmodifiable unless a certain flag, bytecode, opcode, etc., precedes or delimits the instruction sequence. The default may be for the code to be modifiable unless marked and marking involves inserting delimiters around instructions sequences that should not be modified. For example, instruction sequences that include external object references and do not satisfy the above inequality are marked as read-only. Therefore, at runtime, the runtime linker uses a runtime linking table (e.g., a procedure link table) because the runtime linker cannot perform relocation processing on instruction sequences marked as read-only.

FIG. 1Bdepicts an optimization tool moving sections of code according to some realizations of the invention. InFIG. 1B, a code unit107includes runtime linked external object references, similar toFIG. 1A. However, the code unit107includes a modifiable section, unlike the code unit101inFIG. 1A. The modifiable section may be created by the optimization tool111, may be created by a different software tool, may have been a part of the originally generated code unit107, etc. The code unit107also has corresponding performance information109, as withFIG. 1A. Similar toFIG. 1A, an optimization tool111retrieves the performance information109and utilizes the performance information to determine whether modifying a runtime linked external object reference to indicate the runtime location of the external object is more efficient than repeatedly resolving the external object reference. Instead of marking the code unit101, the optimization tool111moves those external object references that are more efficient to modify to the modifiable section of the code unit107, and modifications for referencing the moved instruction sequences are made to the code unit107. Code units may be modifiable and include an un-modifiable section and realizations move those runtime linked external object references that are not relocation processing candidates to the un-modifiable sections. The optimization tool depicted inFIGS. 1A-1Bmay be part of a software development package, a compiler package, a stand-alone tool, etc.

Selectively indicating which runtime linked external object references should be modified and which should not be modified provides more control over program performance, with respect to runtime linking. This manipulation of runtime linking allows a developer to balance runtime linking overhead against runtime performance. In addition, limiting modification of runtime linked external object references to those that provide improved runtime performance, balances runtime optimization against sharability of the external objects. Without sharability of the external objects, each process that utilizes the external objects would possess its own copy, thus affecting application performance and memory footprint.

Selectively moving the code that requires runtime relocation processing to a modifiable section, while leaving the rest of the code unmodifiable, addresses the sharablility issue of the code unit (executable/shared object) by making only part of the code unsharable, which is relevant for shared objects.

FIG. 2depicts a flowchart for indicating which code sections include runtime link optimization candidate external object references according to some realizations of the invention. At block201, a first code section is processed. At block203, it is determined if the code section includes an external object reference. If the code section does not include an external object reference, then control flows to block205. If the code section includes an external object reference, then control flows to block209.

At block205, it is determined if an end of file is encountered (or end of code unit). If the end of file is encountered, then control flows to block217, where optimization processing exits. If the end of file is not encountered, then control flows to block207.

At block207, the next code section is processed. Control flows from block207back to block203.

At block209, the performance information that corresponds to the code section is retrieved. At block211, it is determined if it is more efficient to perform relocation processing according to the performance information. If it is not more efficient to perform relocation processing, then control flows to block205. If it is more efficient to perform relocation processing, then control flows to block213. At block213, the code section is indicated as modifiable (writeable). Control flows from block213to block205.

While the flow diagram shows a particular order of operations performed by certain realizations of the invention, it should be understood that such order is exemplary (e.g., alternative realizations may perform the operations in a different order, combine certain operations, overlap certain operations, perform certain operations in parallel, etc.). For example, code unit sections may not be processed sequentially or individually. In addition, realizations of the invention process code unit sections that include multiple external object references and determine whether optimization should be performed on the code unit section based at least in part on summing the performance information of all of the external object references for a code unit section. In addition, various realizations of the invention operate on different granularities of code. For example, a code is parsed into lexical tokens and the appropriate lexical tokens, which correspond to runtime linked external object references, are tagged to indicate they are modifiable.

The following provides an example of optimizing code by selectively modifying code sections. Assume that a printf statement will be executed frequently enough to satisfy the previously discussed inequality. Code that includes a call to the printf statement would change as follows:

call printf [PLT]→call printf

If the first function call were encountered, then a procedure link table would be used to find printf (call with redirection). If the second printf is encountered without the [PLT] designation, then relocation processing is performed on the printf statement. A scenario that involves software limited by hardware (e.g., 64-bit instructions executed on a 32-bit platform), may involve relatively greater modification. For example, the following illustrates relocation processing on a call to an external function printf when a call instruction submits to address spanning limitations. The following
call printf [PLT]
is converted to

The next example provides example code for relocating an external object that is an external variable k. Assume that a global offset table (GOT) is utilized. A runtime linker places the external objects into the GOT. To access an external data object during execution, object addresses from the GOT are loaded into execution space and then the objects are loaded. The following example code:

sethi % hi(k), % g1!relocation refers to absoluteaddress !of k (known only atruntime)ld [% g1 + % lo(k)], % o0!just one load to get value of k in!% o0
or converted to the following to address span limitations:
sethi % hh(k), % g1
or % g1, % hm(k), % g1
sllx % g1, 32, % g1
sethi % lm(k), % o1
or % g1, % o1, % g1
ld [% g1+% lo(k)], % o0
For position independent code, a compiler generates instruction sequences for getting the address of the GOT for every function that references external data objects. If every GOT data reference in a given function is modified by relocation processing, then the GOT instruction sequences can be eliminated. Although the examples utilize Solaris® based code, realizations of the invention are not limited to any particular platform or language.

FIGS. 3A-3Bdepict execution of a code unit according to some realizations of the invention.FIG. 3Adepicts a runtime linker operating on an executing code unit that includes a marked external object reference according to some realizations of the invention. A runtime linker301corresponds to a code unit's execution space302. The runtime linker301encounters a marked code unit section305that includes an external object reference. The external object reference305is marked as modifiable. The runtime linker301locates the corresponding external object311in the execution space302. The runtime linker301then modifies the external object reference305to indicate the runtime location of the external object311(e.g., virtual address, physical address, page number and offset, etc.). The runtime linker301then encounters a code unit section307, which is not marked as modifiable, that includes an external object reference. The runtime linker301locates an external object309that corresponds to the external object reference307. The runtime linker301updates a runtime link table303to indicate the runtime location of the external object309.

FIG. 3Bdepicts execution of a code unit after the runtime linker has modified an external object reference according to some realizations of the invention. InFIG. 3B, the code unit section that includes the external object reference305, which has been modified to indicate runtime location of the corresponding external object, is executed 30 times. Each time the code unit section that includes the external object reference305is encountered, execution references the runtime location of the external object309. The code unit section307that includes the external object reference is illustrated as being executed twice. Each time the code unit section307is executed, the runtime link table303is accessed. With the runtime link table303, the external object reference of code section307is resolved to the runtime location of the external object309.

Although time is initially spent modifying the code section305, that time is insignificant compared to the amount of time that would have been spent resolving the external object reference with the runtime link table303each time that code section is encountered during runtime. Likewise, the time spent resolving the external object reference in the code section307both times it is encountered is less than the time that may have been spent modifying the code section307. Runtime linking overhead is reduced for the most frequently executed code section, while any possible runtime linking delays suffered by the less frequently executed code section are limited by the limited frequency of execution. Although the illustrations ofFIGS. 3A-3Bsuggest an executable code unit, shared objects may also include references to other external objects, hence the described invention can be applied to executables and/or shared objects (e.g., dynamic libraries).

FIG. 4depicts an exemplary computer system according to some realizations of the invention. A computer system400includes a processor unit401(possibly including multiple processors). The computer system600also includes a system memory407A-407F (e.g., one or more of cache, SRAM DRAM, RDRAM, EDO RAM, DDR RAM, EEPROM, etc.), a system bus403(e.g., LDT, PCI, ISA, etc.), a network interface405(e.g., an ATM interface, an Ethernet interface, a Frame Relay interface, etc.), and a storage device(s)409A-409D (e.g., optical storage, magnetic storage, etc.). Realizations of the invention may include fewer or additional components not illustrated inFIG. 4(e.g., video cards, audio cards, additional network interfaces, peripheral devices, etc.). The processor unit401, the storage device(s)409A-409D, the network interface405, and the system memory407A-407F are coupled to the system bus403. The system memory407A-407F depicted inFIG. 4embodies a software tool, such as an optimization tool. The embodied software tool operates in accordance with the preceding description.

While the invention has been described with reference to various realizations, it will be understood that these realizations are illustrative and that the scope of the invention is not limited to them. Many variations, modifications, additions, and improvements are possible. More generally, realizations in accordance with the present invention have been described in the context of particular realizations. These realizations are meant to be illustrative and not limiting. Accordingly, plural instances may be provided for components described herein as a single instance. Boundaries between various components, operations and data stores are somewhat arbitrary, and particular operations are illustrated in the context of specific illustrative configurations. Other allocations of functionality are envisioned and may fall within the scope of claims that follow. Finally, structures and functionality presented as discrete components in the exemplary configurations may be implemented as a combined structure or component. These and other variations, modifications, additions, and improvements may fall within the scope of the invention as defined in the claims that follow.