Dynamic Linking

This section describes the object file information and system actions that create running programs. Some information here applies to all systems; information specific to one processor resides in sections marked accordingly.

Executable and shared object files statically represent programs. To execute such programs, the system uses the files to create dynamic program representations, or process images. A process image has segments that contain its text, data, stack, and so on. The major subsections of this section are:

• "Program Header" describes object file structures that are directly involved in program execution. The primary data structure, a program header table, locates segment images in the file and contains other information needed to create the memory image of the program.

• "Program Loading (Processor-Specific)" describes the information used to load a program into memory.

• "Runtime Linker" describes the information used to specify and resolve symbolic references among the object files of the process image.

Program Header

An executable or shared object file's program header table is an array of structures, each describing a segment or other information the system needs to prepare the program for execution. An object file segment contains one or more sections, as described in "Segment Contents".

Program headers are meaningful only for executable and shared object files. A file specifies its own program header size with the ELF header's e_phentsize and e_phnum members. See "ELF Header" for more information.

A program header has the following structure (defined in sys/elf.h):

typedef struct {
        Elf32_Word      p_type;
        Elf32_Off       p_offset;
        Elf32_Addr      p_vaddr;
        Elf32_Addr      p_paddr;
        Elf32_Word      p_filesz;
        Elf32_Word      p_memsz;
        Elf32_Word      p_flags;
        Elf32_Word      p_align;
} Elf32_Phdr;

p_type

This member tells what kind of segment this array element describes or how to interpret the array element's information. Type values and their meanings are specified in Table 7-27.

p_offset

This member gives the offset from the beginning of the file at which the first byte of the segment resides.

p_vaddr

This member gives the virtual address at which the first byte of the segment resides in memory.

p_paddr

On systems for which physical addressing is relevant, this member is reserved for the segment's physical address. Because the system ignores physical addressing for application programs, this member has unspecified contents for executable files and shared objects.

p_filesz

This member gives the number of bytes in the file image of the segment; it may be zero.

p_memsz

This member gives the number of bytes in the memory image of the segment; it may be zero.

p_flags

This member gives flags relevant to the segment. Defined flag values appear below.

p_align

As "Program Loading (Processor-Specific)" describes, loadable process segments must have congruent values for p_vaddr and p_offset, modulo the page size. This member gives the value to which the segments are aligned in memory and in the file. Values 0 and 1 mean no alignment is required. Otherwise, p_align should be a positive, integral power of 2, and p_vaddr should equal p_offset, modulo p_align.

Some entries describe process segments; others give supplementary information and do not contribute to the process image. Segment entries may appear in any order, except as explicitly noted below. Defined type values follow; other values are reserved for future use.

PT_NULL

The array element is unused; other members' values are undefined. This type lets the program header table contain ignored entries.

PT_LOAD

The array element specifies a loadable segment, described by p_filesz and p_memsz. The bytes from the file are mapped to the beginning of the memory segment. If the segment's memory size (p_memsz) is larger than the file size (p_filesz), the extra bytes are defined to hold the value 0 and to follow the segment's initialized area. The file size may not be larger than the memory size. Loadable segment entries in the program header table appear in ascending order, sorted on the p_vaddr member.

PT_DYNAMIC

The array element specifies dynamic linking information. See "Dynamic Section" for more information.

PT_INTERP

The array element specifies the location and size of a null-terminated path name to invoke as an interpreter. This segment type is meaningful only for executable files (though it may occur for shared objects); it may not occur more than once in a file. If it is present, it must precede any loadable segment entry. See "Program Interpreter" for further information.

PT_NOTE

The array element specifies the location and size of auxiliary information. See "Note Section" for details.

PT_SHLIB

This segment type is reserved but has unspecified semantics.

PT_PHDR

The array element, if present, specifies the location and size of the program header table itself, both in the file and in the memory image of the program. This segment type may not occur more than once in a file. Moreover, it may occur only if the program header table is part of the memory image of the program. If it is present, it must precede any loadable segment entry. See "Program Interpreter" for further information.

PT_LOPROC - PT_HIPROC

Values in this inclusive range are reserved for processor-specific semantics.

Unless specifically required elsewhere, all program header segment types are optional. That is, a file's program header table may contain only those elements relevant to its contents.

Base Address

Executable and shared object files have a base address, which is the lowest virtual address associated with the memory image of the program's object file. One use of the base address is to relocate the memory image of the program during dynamic linking.

An executable or shared object file's base address is calculated during execution from three values: the memory load address, the maximum page size, and the lowest virtual address of a program's loadable segment. As "Program Loading (Processor-Specific)" describes, the virtual addresses in the program headers might not represent the actual virtual addresses of the program's memory image.

To compute the base address, you determine the memory address associated with the lowest p_vaddr value for a PT_LOAD segment. You then obtain the base address by truncating the memory address to the nearest multiple of the maximum page size. Depending on the kind of file being loaded into memory, the memory address might or might not match the p_vaddr values.

Segment Permissions

A program to be loaded by the system must have at least one loadable segment (although this is not required by the file format). When the system creates loadable segments' memory images, it gives access permissions as specified in the p_flags member. All bits included in the PF_MASKPROC mask are reserved for processor-specific semantics.

If a permission bit is 0, that type of access is denied. Actual memory permissions depend on the memory management unit, which may vary from one system to another. Although all flag combinations are valid, the system may grant more access than requested. In no case, however, will a segment have write permission unless it is specified explicitly. The following figure shows both the exact flag interpretation and the allowable flag interpretation.

For example, typical text segments have read and execute, but not write permissions. Data segments normally have read, write, and execute permissions.

Segment Contents

An object file segment comprises one or more sections, though this fact is transparent to the program header. Whether the file segment holds one or many sections also is immaterial to program loading. Nonetheless, various data must be present for program execution, dynamic linking, and so on. The diagrams below illustrate segment contents in general terms. The order and membership of sections within a segment may vary; moreover, processor-specific constraints may alter the examples below.

Text segments contain read-only instructions and data, in sections described earlier in this chapter. Data segments contain writable data and instructions. See Table 7-14 for a list of all special sections. Use dump(1) to see which sections are in a particular executable file.

A PT_DYNAMIC program header element points at the .dynamic section, as explained in "Dynamic Section" later. The .got and .plt sections also hold information related to position-independent code and dynamic linking.

The .plt may reside in a text or a data segment, depending on the processor. See "Global Offset Table (Processor-Specific)" and "Procedure Linkage Table (Processor-Specific)" for details.

As previously described on Table 7-10, the .bss section has the type SHT_NOBITS. Although it occupies no space in the file, it contributes to the segment's memory image. Normally, these uninitialized data reside at the end of the segment, thereby making p_memsz larger than p_filesz in the associated program header element.

Program Loading (Processor-Specific)

As the system creates or augments a process image, it logically copies a file's segment to a virtual memory segment. When, and if, the system physically reads the file depends on the program's execution behavior, system load, and so forth.

A process does not require a physical page unless it references the logical page during execution, and processes commonly leave many pages unreferenced. Therefore delaying physical reads frequently obviates them, improving system performance. To obtain this efficiency in practice, executable and shared object files must have segment images whose file offsets and virtual addresses are congruent, modulo the page size.

Virtual addresses and file offsets for SPARC segments are congruent modulo 64K (0x10000). Virtual addresses and file offsets for x86 segments are congruent modulo 4K (0x1000). By aligning segments to the maximum page size, the files are suitable for paging regardless of physical page size.

The following example presents the SPARC version.

Figure 7-7 SPARC: Executable File (64 K alignment)

The following example presents the x86 version.

Figure 7-8 x86: Executable File (4 K alignment)

Although the example's file offsets and virtual addresses are congruent modulo the maximum page size for both text and data, up to four file pages hold impure text or data (depending on page size and file system block size).

• The first text page contains the ELF header, the program header table, and other information.

• The last text page holds a copy of the beginning of data.

• The first data page has a copy of the end of text.

• The last data page may contain file information not relevant to the running process. Logically, the system enforces the memory permissions as if each segment is complete and separate; segments' addresses are adjusted to ensure each logical page in the address space has a single set of permissions. In the examples above, the region of the file holding the end of text and the beginning of data will be mapped twice: at one virtual address for text and at a different virtual address for data.

The end of the data segment requires special handling for uninitialized data, which the system defines to begin with zero values. Thus, if a file's last data page includes information not in the logical memory page, the extraneous data must be set to zero, not the unknown contents of the executable file.

Impurities in the other three pages are not logically part of the process image; whether the system expunges them is unspecified. The memory image for this program follows, assuming 4 Kilobyte (0x1000) pages. For simplicity, these examples illustrates only one page size.

Figure 7-9 SPARC: Process Image Segments

Figure 7-10 x86: Process Image Segments

One aspect of segment loading differs between executable files and shared objects. Executable file segments typically contain absolute code. For the process to execute correctly, the segments must reside at the virtual addresses used to build the executable file. Thus the system uses the p_vaddr values unchanged as virtual addresses.

On the other hand, shared object segments typically contain position-independent code. (For background, see Chapter 2, Link-Editor.) This lets a segment's virtual address change from one process to another, without invalidating execution behavior.

Though the system chooses virtual addresses for individual processes, it maintains the segments' relative positions. Because position-independent code uses relative addressing between segments, the difference between virtual addresses in memory must match the difference between virtual addresses in the file.

The following tables show possible shared object virtual address assignments for several processes, illustrating constant relative positioning. The table also illustrates the base address computations.

Program Interpreter

An executable file may have one PT_INTERP program header element. During exec(2), the system retrieves a path name from the PT_INTERP segment and creates the initial process image from the interpreter file's segments. That is, instead of using segment images of the original executable files, the system composes a memory image for the interpreter. It then is the interpreter's responsibility to receive control from the system and provide an environment for the application program.

The interpreter receives control in one of two ways. First, it may receive a file descriptor to read the executable file, positioned at the beginning. It can use this file descriptor to read and/or map the executable file's segments into memory. Second, depending on the executable file format, the system may load the executable file into memory instead of giving the interpreter an open file descriptor.

With the possible exception of the file descriptor, the interpreter's initial process state matches what the executable file has received. The interpreter itself may not require a second interpreter. An interpreter may be either a shared object or an executable file.

• A shared object (the normal case) is loaded as position-independent, with addresses that may vary from one process to another; the system creates its segments in the dynamic segment area used by mmap(2) and related services. Consequently, a shared object interpreter typically will not conflict with the original executable file's original segment addresses.

• An executable file is loaded at fixed addresses; the system creates its segments using the virtual addresses from the program header table. Consequently, an executable file interpreter's virtual addresses may collide with the first executable file; the interpreter is responsible for resolving conflicts.

Runtime Linker

When building an executable file that uses dynamic linking, the link-editor adds a program header element of type PT_INTERP to an executable file, telling the system to invoke the runtime linker as the program interpreter. exec(2) and the runtime linker cooperate to create the process image for the program, which entails the following actions:

• Adding the executable file's memory segments to the process image.

• Adding shared object memory segments to the process image.

• Performing relocations for the executable file and its shared objects.

• Closing the file descriptor that was used to read the executable file, if one was given to the runtime linker.

• Calling any .init section provided in the objects mapped. See "Initialization and Termination Functions".

• Transferring control to the program, making it look as if the program had received control directly from exec(2).

The link-editor also constructs various data that assist the runtime linker for executable and shared object files. As shown above in "Program Header," these data reside in loadable segments, making them available during execution. (Once again, recall the exact segment contents are processor-specific.)

• A .dynamic section with type SHT_DYNAMIC holds various data. The structure residing at the beginning of the section holds the addresses of other dynamic linking information.

• The .hash section with type SHT_HASH holds a symbol hash table.

• The .got and .plt sections with type SHT_PROGBITS hold two separate tables: the global offset table and the procedure linkage table. Sections below explain how the runtime linker uses and changes the tables to create memory images for object files.

As explained in "Program Loading (Processor-Specific)", shared objects may occupy virtual memory addresses that are different from the addresses recorded in the file's program header table. The runtime linker relocates the memory image, updating absolute addresses before the application gains control. Although the absolute address values will be correct if the library is loaded at the addresses specified in the program header table, this normally is not the case.

If the process environment (see exec(2) contains a variable named LD_BIND_NOW with a non-null value, the runtime linker processes all relocation before transferring control to the program. For example, each of the environment entries:

LD_BIND_NOW=1
LD_BIND_NOW=on
LD_BIND_NOW=off

specifies this behavior. The runtime linker can evaluate procedure linkage table entries lazily, so avoiding resolution and relocation overhead for functions that are not called. See "Procedure Linkage Table (Processor-Specific)" for more information.

Dynamic Section

If an object file participates in dynamic linking, its program header table will have an element of type PT_DYNAMIC. This segment contains the .dynamic section. A special symbol, _DYNAMIC, labels the section, which contains an array of the following structures (defined in sys/link.h):

typedef struct {
        Elf32_Sword d_tag;
        union {
                Elf32_Word      d_val;
                Elf32_Addr      d_ptr;
                Elf32_Off       d_off;
        } d_un;
} Elf32_Dyn;

For each object with this type, d_tag controls the interpretation of d_un.

d_val

These Elf32_Word objects represent integer values with various interpretations.

d_ptr

These Elf32_Addr objects represent program virtual addresses. As mentioned previously, a file's virtual addresses might not match the memory virtual addresses during execution. When interpreting addresses contained in the dynamic structure, the runtime linker computes actual addresses, based on the original file value and the memory base address. For consistency, files do not contain relocation entries to correct addresses in the dynamic structure.

The following table summarizes the tag requirements for executable and shared object files. If a tag is marked mandatory, then the dynamic linking array must have an entry of that type. Likewise, optional means an entry for the tag may appear but is not required.

DT_NULL

An entry with a DT_NULL tag marks the end of the _DYNAMIC array.

DT_NEEDED

This element holds the string table offset of a null-terminated string, giving the name of a needed dependency. The offset is an index into the table recorded in the DT_STRTAB entry. See "Shared Object Dependencies" for more information about these names. The dynamic array may contain multiple entries with this type. These entries' relative order is significant, though their relation to entries of other types is not.

DT_PLTRELSZ

This element holds the total size, in bytes, of the relocation entries associated with the procedure linkage table. If an entry of type DT_JMPREL is present, a DT_PLTRELSZ must accompany it.

DT_PLTGOT

This element holds an address associated with the procedure linkage table and/or the global offset table.

DT_HASH

This element points to the symbol hash table, described in "Hash Table". This hash table refers to the symbol table indicated by the DT_SYMTAB element.

DT_STRTAB

This element holds the address of the string table, described in the first part of this chapter. Symbol names, dependency names, and other strings required by the runtime linker reside in this table.

DT_SYMTAB

This element holds the address of the symbol table, described in the first part of this chapter, with Elf32_Sym entries for the 32-bit class of files.

DT_RELA

This element holds the address of a relocation table, described in the first part of this chapter. Entries in the table have explicit addends, such as Elf32_Rela for the 32-bit file class.

An object file may have multiple relocation sections. When building the relocation table for an executable or shared object file, the link-editor catenates those sections to form a single table. Although the sections remain independent in the object file, the runtime linker sees a single table. When the runtime linker creates the process image for an executable file or adds a shared object to the process image, it reads the relocation table and performs the associated actions.

If this element is present, the dynamic structure must also have DT_RELASZ and DT_RELAENT elements. When relocation is mandatory for a file, either DT_RELA or DT_REL may occur (both are permitted but not required).

DT_RELASZ

This element holds the total size, in bytes, of the DT_RELA relocation table.

DT_RELAENT

This element holds the size, in bytes, of the DT_RELA relocation entry.

DT_STRSZ

This element holds the size, in bytes, of the string table.

DT_SYMENT

This element holds the size, in bytes, of a symbol table entry.

DT_INIT

This element holds the address of the initialization function, discussed in "Initialization and Termination Functions" later.

DT_FINI

This element holds the address of the termination function, discussed in "Initialization and Termination Functions" later.

DT_SONAME

This element holds the string table offset of a null-terminated string, giving the name of the shared object. The offset is an index into the table recorded in the DT_STRTAB entry. See "Shared Object Dependencies" for more information about these names.

DT_RPATH

This element holds the string table offset of a null-terminated search library search path string, discussed in "Shared Objects with Dependencies". The offset is an index into the table recorded in the DT_STRTAB entry.

DT_SYMBOLIC

This element's presence in a shared object library alters the runtime linker's symbol resolution algorithm for references within the library. Instead of starting a symbol search with the executable file, the runtime linker starts from the shared object itself. If the shared object fails to supply the referenced symbol, the runtime linker then searches the executable file and other shared objects as usual.

DT_REL

This element is similar to DT_RELA, except its table has implicit addends, such as Elf32_Rel for the 32-bit file class. If this element is present, the dynamic structure must also have DT_RELSZ and DT_RELENT elements.

DT_RELSZ

This element holds the total size, in bytes, of the DT_REL relocation table.

DT_RELENT

This element holds the size, in bytes, of the DT_REL relocation entry.

DT_PLTREL

This member specifies the type of relocation entry to which the procedure linkage table refers. The d_val member holds DT_REL or DT_RELA, as appropriate. All relocations in a procedure linkage table must use the same relocation.

DT_DEBUG

This member is used for debugging.

DT_TEXTREL

This member's absence signifies that no relocation entry should cause a modification to a non-writable segment, as specified by the segment permissions in the program header table. If this member is present, one or more relocation entries might request modifications to a non-writable segment, and the runtime linker can prepare accordingly.

DT_FLAGS_1

If present, this entry's d_val member holds various state flags. See Table 7-35.

DT_JMPREL

If present, this entry's d_ptr member holds the address of relocation entries associated solely with the procedure linkage table. Separating these relocation entries lets the runtime linker ignore them during process initialization, if lazy binding is enabled. If this entry is present, the related entries of types DT_PLTRELSZ and DT_PLTREL must also be present.

DT_VERDEF

Holds the address of the version definition table, described in the first part of this chapter, with Elf32_Verdef entries for the 32-bit class of files. See section "Version Definition Section"for more information. Elements within these entries contain indexes into the table recorded in the DT_STRTAB entry.

DT_VERDEFNUM

This element specifies the number of entries in the version definition table.

DT_VERNEED

Holds the address of the version dependency table, described in the first part of this chapter, with Elf32_Verneed entries for the 32-bit class of files. See section "Version Dependency Section" for more information. Elements within these entries contain indexes into the table recorded in the DT_STRTAB entry.

DT_VERNEEDNUM

This element specifies the number of entries in the version dependency table.

DT_AUXILIARY

Holds the string table offset of a null-terminated string that names an object. The offset is an index into the table recorded in the DT_STRTAB entry. Symbols in the auxiliary object will be used in preference to the symbols within this object.

DT_FILTER

Holds the string table offset of a null-terminated string that names an object. The offset is an index into the table recorded in the DT_STRTAB entry. The symbol table of this object acts as a filter for the symbol table of the named object.

DT_LOPROC - DT_HIPROC

Values in this inclusive range are reserved for processor-specific semantics.

The following dynamic state flags are presently available:

DF_1_NOW

When the object is loaded all relocation processing is completed, see "When Relocations are Performed". This state is recorded in the object using the link-editors' -z now option.

DF_1_GROUP

Indicates that the object is a member of a group, see "Symbol Lookup". This state is recorded in the object using the link-editors' -B group option.

DF_1_NODELETE

Indicates that the object can not be deleted from a process. Thus if the object is loaded in a process, either directly or as a dependency, with dlopen(3X), it can not be unloaded with dlclose(3X). This state is recorded in the object using the link-editors' -z nodelete option.

DF_1_LOADFLTR

This state is only meaningful for filters (See "Shared Objects as Filters"). When the filter is loaded all associated filtees are immediately processed, see "Filtee Processing". This state is recorded in the object using the link-editors' -z loadfltr option.

DF_1_INITFIRST

When the object is loaded its initialization section is run before any other objects loaded with it, see "Initialization and Termination Routines". This specialized state is intended for libthread.so.1. This state is recorded in the object using the link-editors' -z initfirst option.

DF_1_NOOPEN

Indicates that the object can not be added to a running process with dlopen(3X). This state is recorded in the object using the link-editors' -z nodlopen option.

Except for the DT_NULL element at the end of the dynamic array and the relative order of DT_NEEDED elements, entries may appear in any order. Tag values not appearing in the table are reserved.

Shared Object Dependencies

When the runtime linker creates the memory segments for an object file, the dependencies (recorded in DT_NEEDED entries of the dynamic structure) tell what shared objects are needed to supply the program's services. By repeatedly connecting referenced shared objects and their dependencies, the runtime linker builds a complete process image.

When resolving symbolic references, the runtime linker examines the symbol tables with a breadth-first search. That is, it first looks at the symbol table of the executable program itself, then at the symbol tables of the DT_NEEDED entries (in order), then at the second level DT_NEEDED entries, and so on.

Even when a shared object is referenced multiple times in the dependency list, the runtime linker will connect the object only once to the process.

Names in the dependency list are copies either of the DT_SONAME strings or the path names of the shared objects used to build the object file.

Global Offset Table (Processor-Specific)

Position-independent code cannot, in general, contain absolute virtual addresses. Global offset tables hold absolute addresses in private data, thus making the addresses available without compromising the position-independence and shareability of a program's text. A program references its global offset table using position-independent addressing and extracts absolute values, thus redirecting position-independent references to absolute locations.

Initially, the global offset table holds information as required by its relocation entries (see "Relocation" for more information). After the system creates memory segments for a loadable object file, the runtime linker processes the relocation entries, some of which will be type R_SPARC_GLOB_DAT (for SPARC), or R_386_GLOB_DAT (for x86) referring to the global offset table.

The runtime linker determines the associated symbol values, calculates their absolute addresses, and sets the appropriate memory table entries to the proper values. Although the absolute addresses are unknown when the link-editor builds an object file, the runtime linker knows the addresses of all memory segments and can thus calculate the absolute addresses of the symbols contained therein.

If a program requires direct access to the absolute address of a symbol, that symbol will have a global offset table entry. Because the executable file and shared objects have separate global offset tables, a symbol's address may appear in several tables. The runtime linker processes all the global offset table relocations before giving control to any code in the process image, thus ensuring the absolute addresses are available during execution.

The table's entry zero is reserved to hold the address of the dynamic structure, referenced with the symbol _DYNAMIC. This allows a program, such as the runtime linker, to find its own dynamic structure without having yet processed its relocation entries. This is especially important for the runtime linker, because it must initialize itself without relying on other programs to relocate its memory image.

The system may choose different memory segment addresses for the same shared object in different programs; it may even choose different library addresses for different executions of the same program. Nonetheless, memory segments do not change addresses once the process image is established. As long as a process exists, its memory segments reside at fixed virtual addresses.

A global offset table's format and interpretation are processor-specific. For SPARC and x86 processors, the symbol _GLOBAL_OFFSET_TABLE_ may be used to access the table.

extern Elf32_Addr  _GLOBAL_OFFSET_TABLE_[];

The symbol _GLOBAL_OFFSET_TABLE_ may reside in the middle of the .got section, allowing both negative and nonnegative subscripts into the array of addresses.

Procedure Linkage Table (Processor-Specific)

As the global offset table converts position-independent address calculations to absolute locations, the procedure linkage table converts position-independent function calls to absolute locations. The link-editor cannot resolve execution transfers (such as function calls) from one executable or shared object to another. So, the link-editor puts the program transfer control to entries in the procedure linkage table.

SPARC: Procedure Linkage Table

On SPARC architectures, procedure linkage tables reside in private data. The runtime linker determines the destinations' absolute addresses and modifies the procedure linkage table's memory image accordingly. The runtime linker thus redirects the entries without compromising the position-independence and shareability of the program's text. Executable files and shared object files have separate procedure linkage tables.

The first four procedure linkage table entries are reserved. (The original contents of these entries are unspecified, despite the example, below.) Each entry in the table occupies 3 words (12 bytes), and the last table entry is followed by a nop instruction.

A relocation table is associated with the procedure linkage table. The DT_JMP_REL entry in the _DYNAMIC array gives the location of the first relocation entry. The relocation table has one entry, in the same sequence, for each procedure linkage table entry. Except the first four entries, the relocation type is R_SPARC_JMP_SLOT, the relocation offset specifies the address of the first byte of the associated procedure linkage table entry, and the symbol table index refers to the appropriate symbol.

To illustrate procedure linkage tables, the figure below shows four entries: two of the four initial reserved entries, the third is a call to name1, and the fourth is a call to name2. The example assumes the entry for name2 is the table's last entry and shows the following nop instruction. The left column shows the instructions from the object file before dynamic linking. The right column demonstrates a possible way the runtime linker might fix the procedure linkage table entries.

.PLT0:
     unimp
	    unimp
	    unimp
.PLT1:
	    unimp
	    unimp
	    unimp
	    ...

.PLT0:
	    save    %sp,-64,%sp
	    call    runtime-linker
	    nop
.PLT1:
	    .word   identification
	    unimp
	    unimp
	    ...

	... 
.PLT101:
	    sethi    (.-.PLT0),%g1
	    ba,a     .PLT0
	    nop
.PLT102:
	    sethi    (.-.PLT0),%g1
	    ba,a     .PLT0
     nop

	...
.PLT101:
	    sethi   (.-.PLT0),%g1
	    sethi   %hi(name1),%g1
	    jmp1    %g1+%lo(name1),%g0
.PLT102:
	    sethi   (.-.PLT0),%g1
	    sethi   %hi(name2),%g1
	    jmp1    %g1+%lo(name2),%g0

     nop

	    nop

Following the steps below, the runtime linker and program jointly resolve the symbolic references through the procedure linkage table. Again, the steps described below are for explanation only. The precise execution-time behavior of the runtime linker is not specified.

1. When first creating the memory image of the program, the runtime linker changes the initial procedure linkage table entries, making them transfer control to one of the runtime linker's own routines. It also stores a word of identification information in the second entry. When it receives control, it can examine this word to find what object called it.

2. All other procedure linkage table entries initially transfer to the first entry, letting the runtime linker gain control at the first execution of each table entry. For example, the program calls name1, which transfers control to the label .PLT101.

3. The sethi instruction computes the distance between the current and the initial procedure linkage table entries, .PLT101 and .PLT0, respectively. This value occupies the most significant 22 bits of the %g1 register. In this example, &g1 contains 0x12f000 when the runtime linker receives control.

4. Next, the ba,a instruction jumps to .PLT0, establishing a stack frame and calls the runtime linker.

5. With the identification value, the runtime linker gets its data structures for the object, including the relocation table.

6. By shifting the %g1 value and dividing by the size of the procedure linkage table entries, the runtime linker calculates the index of the relocation entry for name1. Relocation entry 101 has type R_SPARC_JMP_SLOT, its offset specifies the address of .PLT101, and its symbol table index refers to name1. Thus, the runtime linker gets the symbol's real value, unwinds the stack, modifies the procedure linkage table entry, and transfers control to the desired destination.

Although the runtime linker does not have to create the instruction sequences under the Memory Segment column, it might. If it did, some points deserve more explanation.

• To make the code reentrant, the procedure linkage table's instructions are changed in a particular sequence. If the runtime linker is fixing a function's procedure linkage table entry and a signal arrives, the signal handling code must be able to call the original function with predictable (and correct) results.

• The runtime linker changes two words to convert an entry. It updates each word automatically. Reentrancy is achieved by first overwriting the nop with the jmp1 instruction, and then patching the ba,a to be sethi. If a reentrant function call happens between the two word updates, the jmp1 resides in the delay slot of the ba,a instruction, and cancels the delay instruction. So, the runtime linker gains control a second time. Although both invocations of the runtime linker modify the same procedure linkage table entry, their changes do not interfere with each other.

• The first sethi instruction of a procedure linkage table entry can fill the delay slot of the previous entry's jmp1 instruction. Although the sethi changes the value of the %g1 register, the previous contents can be safely discarded.

• After conversion, the last procedure linkage table entry (.PLT102 above) needs a delay instruction for its jmp1. The required, trailing nop fills this delay slot.

The LD_BIND_NOW environment variable changes dynamic linking behavior. If its value is non-null, the runtime linker processes R_SPARC_JMP_SLOT relocation entries (procedure linkage table entries) before transferring control to the program. If LD_BIND_NOW is null, the runtime linker evaluates linkage table entries on the first execution of each table entry.

x86: Procedure Linkage Table

On x86 architectures, procedure linkage tables reside in shared text, but they use addresses in the private global offset table. The runtime linker determines the destinations' absolute addresses and modifies the global offset table's memory image accordingly. The runtime linker thus redirects the entries without compromising the position-independence and shareability of the program's text. Executable files and shared object files have separate procedure linkage tables.

.PLT0:  pushl   got_plus_4
        jmp     *got_plus_8
        nop;    nop
        nop;    nop
.PLT1:  jmp     *name1_in_GOT
        pushl   $offset
        jmp     .PLT0@PC
.PLT2:  jmp     *name2_in_GOT
        pushl   $offset
        jmp     .PLT0@PC
        ...

.PLT0:  pushl   4(%ebx)
        jmp     *8(%ebx)
        nop;    nop
        nop;    nop
.PLT1:  jmp     *name1@GOT(%ebx)
        pushl   $offset
        jmp     .PLT0@PC
.PLT2:  jmp     *name2@GOT(%ebx)
        pushl   $offset
        jmp     .PLT0@PC
        ...

Following the steps below, the runtime linker and program cooperate to resolve the symbolic references through the procedure linkage table and the global offset table.

1. When first creating the memory image of the program, the runtime linker sets the second and third entries in the global offset table to special values. Steps below explain these values.

2. If the procedure linkage table is position-independent, the address of the global offset table must be in %ebx. Each shared object file in the process image has its own procedure linkage table, and control transfers to a procedure linkage table entry only from within the same object file. So, the calling function must set the global offset table base register before it calls the procedure linkage table entry.

3. For example, the program calls name1, which transfers control to the label .PLT1.

4. The first instruction jumps to the address in the global offset table entry for name1. Initially, the global offset table holds the address of the following pushl instruction, not the real address of name1.

5. So, the program pushes a relocation offset (offset) on the stack. The relocation offset is a 32-bit, nonnegative byte offset into the relocation table. the designated relocation entry has the type R_386_JMP_SLOT, and its offset specifies the global offset table entry used in the previous jmp instruction. The relocation entry also contains a symbol table index, which the runtime linker uses to get the referenced symbol, name1.

6. After pushing the relocation offset, the program jumps to .PLT0, the first entry in the procedure linkage table. The pushl instruction pushes the value of the second global offset table entry (got_plus_4 or 4(%ebx)) on the stack, giving the runtime linker one word of identifying information. The program then jumps to the address in the third global offset table entry (got_plus_8 or 8(%ebx)), to jump to the runtime linker.

7. The runtime linker unwinds the stack, checks the designated relocation entry, gets the symbol's value, stores the actual address of name1 in its global offset entry table, and jumps to the destination.

8. Subsequent executions of the procedure linkage table entry transfer directly to name1, without calling the runtime linker again. This is because the jmp instruction at .PLT1 jumps to name1 instead of falling through to the pushl instruction.

The LD_BIND_NOW environment variable changes dynamic linking behavior. If its value is non-null, the runtime linker processes R_386_JMP_SLOT relocation entries (procedure linkage table entries) before transferring control to the program. If LD_BIND_NOW is null, the runtime linker evaluates linkage table entries on the first execution of each table entry.

Hash Table

A hash table of Elf32_Word objects supports symbol table access. The symbol table to which the hashing is associated is specified in the sh_link entry of the hash table's section header (refer to Table 7-13). Labels appear below to help explain the hash table organization, but they are not part of the specification.

Figure 7-11 Symbol Hash Table

The bucket array contains nbucket entries, and the chain array contains nchain entries; indexes start at 0. Both bucket and chain hold symbol table indexes. Chain table entries parallel the symbol table. The number of symbol table entries should equal nchain; so, symbol table indexes also select chain table entries.

A hashing function accepts a symbol name and returns a value that may be used to compute a bucket index. Consequently, if the hashing function returns the value x for some name, bucket [x%nbucket] gives an index y into both the symbol table and the chain table. If the symbol table entry is not the one desired, chain[y] gives the next symbol table entry with the same hash value.

One can follow the chain links until either the selected symbol table entry holds the desired name or the chain entry contains the value STN_UNDEF.

unsigned long
elf_Hash(const unsigned char *name)
{
    unsigned long h = 0, g;

	    while (*name)
	    {
		     h = (h << 4) + *name++;
		     if (g = h & 0xf0000000)
			      h ^= g >> 24;
				   h &= ~g;
	    }
	    return h;
}

Initialization and Termination Functions

After the runtime linker has built the process image and performed the relocations, each shared object gets the opportunity to execute some initialization code.

Similarly, shared objects may have termination functions, which are executed with the atexit(3C) mechanism after the base process begins its termination sequence. Refer to atexit(3C) for more information.

Shared objects designate their initialization and termination functions through the DT_INIT and DT_FINI entries in the dynamic structure, described in "Dynamic Section" above. Typically, the code for these functions resides in the .init and .fini sections, mentioned in "Sections" earlier.

Although the atexit(3C) termination processing normally will be done, it is not guaranteed to have executed upon process death. In particular, the process will not execute the termination processing if it calls _exit() or if the process dies because it received a signal that it neither caught nor ignored.