Linkers and Loaders

In this post,we will discuss the key features of linkers and loaders.For the clarity in the presentation,we begin with a description of the loading task when a single program module is involved;no linking is required.

Loading

For simplicity, let us assume that the process image occupies a contiguous region of main memory.

Fig. 1

In the above fig., branch instructions contain an address to reference the instruction to be executed next. Data reference instructions contain the address of the byte or word of data referenced.

In Fig.3, the loader places the load module in main memory starting at location x.In loading the program,assume that process image occupies a contiguous region of memory,as explained above.

Fig. 2

Fig. 3

.

In general, three approaches can be taken:

• Absolute loading
• Relocatable loading
• Dynamic run-time loading

Absolute Loading:

An absolute loader requires that a given load module always be loaded into the same location in main memory.

In the load module presented to the loader,all address references are absolute i.e. main memory addresses.The assignment of specific address values to memory references within a program can be done either by the programmer or at compile or assembly time.There are several disadvantages of this approach.The main disadvantage of binding memory references to specific addresses prior to loading is that the resulting load module can only be placed in one region of main memory.However,when many programs share main memory,it may not be desirable to decide ahead of time into which region of memory a particular module should be loaded. It is better to make that decision at load time so that load module can be located anywhere in main memory.And because of this requirement relocatable loader is required.

Fig. 4

Relocatable Loading:

The disadvantage of binding memory references to specific addresses prior to loading is that the resulting load module can only be placed in one region of main memory. However, when many programs share main memory, it may not be desirable to decide ahead of time into which region of memory a particular module should be loaded. It is better to make that decision at load time.Thus we need a load module that can be located anywhere in main memory.

To satisfy this new requirement, the assembler or compiler produces not actual main memory addresses(absolute addresses) but addresses that are relative to some known point, such as the start of the program. This technique is illustrated in Fig. 5. 

Fig. 5

The start of the load module is assigned the relative address 0, and all other memory references within the module are expressed relative to the beginning of the module.

With all memory references expressed in relative format, it becomes a simple task for the loader to place the module in the desired location. If the module is to be loaded beginning at location x, then the loader must simply add x to each memory references as it loads the module into memory. To assist in this task, the load module must include information that tells the loader where the address references are and how they are to be interpreted(usually relative to the program origin). This set of information is prepared by the compiler or assembler and is usually referred to as the relocation dictionary.

The main disadvantage of this technique is that memory references are bound to absolute address at the initial load time.And because of this dynamic loading comes into picture.This disadvantage is described in greater detail in dynamic run-time loading section.

Dynamic Run-Time Loading:

Relocatable loaders are common and provide obvious benefits relative to absolute loaders. However, in a multiprogramming environment, even one that does not depends on virtual memory, the relocatable lading scheme is inadequate. We have referred to the need to swap process images in and out of main memory to maximize the utilization of the processor. To maximize main memory utilization, we would like to be able to swap the process image back into different locations at different times. Thus, a program once loaded, may be swapped out to disk and then swapped back in at a different location.This would be impossible if memory references had been bound to absolute addresses at the initial load time.

The alternative is to defer the calculation of an absolute address until it is actually needed at run time.For this purpose, the load module is loaded into main memory with all memory references in relative form.It is not until an instruction is actually executed that the absolute address is calculated. To assure that this function does not degrade performance, it must be done by special processor hardware rather than software.

Dynamic address calculation provides complete flexibility. A program can be loaded into any region of main memory.Subsequently, the execution of the program can be interrupted and the program can be swapped out to main memory, to be later swapped back in at a different location.

Table 1

Linking

The function of a linker is to take as input a collection of object modules and produce a load module to be passes to the loader.In each object module, there may be address references to locations in other modules. Each such reference can only be expressed symbolically in an unlinked object module. The linker creates a single load module that is the contiguous joining of all of the object modules. Each intramodule reference must be changed from a symbolic address to a reference to a location within the overall load module. For example,module A in fig. 6 contains a procedure invocation of module B. When these modules are combined in the load module, this symbolic reference to module B is changed to a specific reference to the location of the entry point of B within the load module.

Fig. 6

Linkage Editor:

The nature of this address linkage will depend on the type of load module to be created and when the linkage occurs(Table 2).If,as is usually the case, a relocatable load module is desired, then linkage is usually done in the following fashion.

Each compiled or assembled object module is created with references relative to the beginning of the object module. All of these modules are put together into a single relocatable load module with all the references relative to the origin of the load module.This module can be used as input for relocatable loading or dynamic run-time loading.

Dynamic Linker:

Dynamic linker creates the load module that contains unresolved references to other programs. These references can be resolved either at load time or run time.

Load-time dynamic linking:

The load module(application module) to be loaded is read into memory. Any references to an external module causes the loader to find the target module, load it, and alter the reference to a relative address in memory from the beginning of the application module(load module).

Advantages of load-time dynamic linking:

1. It becomes easier to incorporate changed or upgraded versions of the target module, which may be an operating system utility or some other general-purpose routine. With static linking, a change to such a supporting module would require the relinking of the entire application module.Not only is this inefficient, but it may be impossible in some circumstances. For example most commercial softwares are released in load module form; source and object versions are not released.
2. Code sharing.The operating system can recognize that more than one application is using the same target code because it loaded and linked that code. It can use that information to load a single copy of the target code and link it to both applications, rather than having to load one copy for each application.
3. It becomes easier for independent software developers to extend the functionality of a widely used OS such as Linux. A developer can come up with a new function that may be useful to a variety of applications and package it as dynamic link module.

Run-time dynamic linking:

 With run-time dynamic linking, some of the linking is posponed until execution time.That is, rather than load time linking,external references are resolved during execution time. External references to target module remains in the loaded program. When a call is made to the absent module, the OS locates the module, loads it, and links it to the calling module. Such modules are typically shareable.

In windows environment these are called as dynamic link libraries(DLLs). Thus, if one process is already making use of a dynamically-linked shared module, then that module is in main memory and a new process can simply link to the already-loaded module.

Advantages of run-time dynamic linking:

• Use of such a dynamic linker is that it is not necessary to allocate memory for programs units unless those units are referenced.

Table 2.