Module 4.

Loaders and Linkers

1
 Introduction to Linkers

● Linking is a process of collecting and maintaining piece of code and data

into a single file.
● Linker program helps to link object modules of a program into a single
object file.
● It performs the process of linking. Linkers are also called as link editors.
● Linker also links a particular module into system library.
● It takes object modules from assembler as input and forms an executable
file as output for the loader.

2
 Introduction to Linkers

● Linking is performed at compile time, when the source code is translated

into machine code and load time, when the program is loaded into memory
by the loader.
Source code -> compiler -> Assembler -> Object code -> Linker ->
Executable file -> Loader

3
Introduction to Linkers: Linker Program

4
 Introduction to Linkers

● Linking is performed at
− compile time, when the source code is translated into machine code

− and load time, when the program is loaded into memory by the loader.
Source code -> compiler -> Assembler -> Object code -> Linker -> Executable file ->
Loader
● Linking is of two types:
− Static Linking

− Dynamic linking

5
 Introduction to Linkers
1. Static Linking
● It is performed during the compilation of source program.

● Linking is performed before execution in static linking.

● It takes collection of relocatable object file and command-line arguments

and generates a fully linked object file that can be loaded and run.

● Static linker performs two major tasks:

− Symbol resolution – It associates each symbol reference with exactly

one symbol definition. Every symbol has a predefined task.

− Relocation – It relocates code and data section and modifies the symbol
6
7
 Introduction to Linkers: Static Linking continued...

● The linker copies all library routines used in the program into executable
image.
● It requires more memory space.

● As it does not require the presence of library on the system when it is run,
so it is faster and more portable.

● No failure chance and less error chance

8
 Introduction to Linkers: 2. ` linking
2. Dynamic linking –
● Dynamic linking is performed during the run time.
● This linking is accomplished by placing the name of a shareable library in
the executable image.
● There are more chances of errors and failures.
● It require less memory space as multiple programs can share a single copy
of the library.
● Here we can perform code sharing.

9
 Introduction to Linkers : 2. Dynamic linking continued....

2. Dynamic linking –
● If we are using the same object a number of times in the program,
instead of linking the same object again and again into the library, each
module shares information of the object with other modules having the
same object.
● The shared library needed in the linking is stored in virtual memory to
save RAM.
● In this linking we can also relocate the code for the smooth running of
code but all the code is not relocatable. It fixes the address at run time.

10
 Introduction to Loaders

● Loader is a program that is responsible for loading executable programs

into memory for execution.
● The loader reads the object code of a program, which is usually in binary
form, and copies it into memory.
● It also performs other tasks such as allocating memory for the program’s
data and resolving any external references to other programs or libraries.

11
Introduction to Loaders: A general loading scheme

12
 Functions of Loaders

Loader performs its task via four functions, these are as follows:
● Allocation: It allocates memory for the program in the main memory.
● Linking: It combines two or more separate object programs or modules
and supplies necessary information.
● Relocation: It modifies the object program so that it can be loaded at an
address different from the location.
● Loading: It brings the object program into the main memory for
execution.

13
 Functions of Loaders: 1. Allocation

In order to allocate memory to the program, the loader allocates the

memory on the basis of the size of the program, this is known as
allocation.
● The loader gives the space in memory where the object program will be
loaded for execution.

14
 Functions of Loaders: 2. Linking

● The linker resolves the symbolic reference code or data between the
object modules.
● It allocates all of the user subroutine and library subroutine the
addresses.
● This process is known as linking.
● In any language, a program written has a function, it can be user-defined
or can be a library function.
● For example, in C language we have a printf() function.
● When the program control goes to the line where the printf() is written,
15
 Functions of Loaders: 3.Relocation

● There are some address-dependent locations in the program, and

these address constants must be modified to fit the available
space.
● This can be done by loader and this is known as relocation.
● In order to allow the object program to be loaded at a different
address loader modifies the object program by modifying
specific instructions.

16
 Functions of Loaders: 4. Loading

● The loader loads the program into the main memory for
execution of that program.
● It loads machine instruction and data of related programs
and subroutines into the main memory, this process is
known as loading.
● The loader performs loading; hence, the assembler must
provide the loader with the object program.

17
 Difference between Loader and Linker

Linker Loader

The main function of Linker is to generate executable Main objective of Loader is to load executable files to
files. main memory.
The linker takes input of object code generated by Loader takes input of executable files generated by
compiler/assembler. linker.
Linking can be defined as process of combining Loading can be defined as process of loading
various pieces of codes and source code to obtain executable codes to main memory for further execution.
executable code.

Linkers are of 2 types: Linkage Editor and Dynamic Loaders are of 4 types: Absolute, Relocating, Direct
Linker. Linking, Bootstrap Loader.
Another use of linker is to combine all object modules. It helps in allocating the address to executable
codes/files.
Linker is also responsible for arranging objects in Loader is also responsible for adjusting references
program’s address space. which are used within the program.

18
 Absolute Loader

● The absolute loader is a kind of loader in

which relocated object files are created,
loader accepts these files and places them
at a specified location in the memory.
● This type of loader is called absolute loader
19
 Absolute Loader

● In this scheme, the programmer or assembler should have knowledge of

memory management.
● The programmer should take care of two things:
● Specification of starting address of each module to be used.
– If some modification is done in some module then the length of that
module may vary.
– This causes a change in the starting address of immediate next
modules, it's then the programmer's duty to make necessary changes
in the starting address of respective modules.
– While branching from one segment to another the absolute starting
address of respective module is to be known by the programmer so
that such address can be specified at respective JMP instruction.

20
Process of Absolute Loader

21
 Advantages of Absolute Loader

● It is simple to implement.
● This scheme allows multiple programs or the source programs written in
different languages.
● If there are multiple programs written in different languages then the
respective language assembler will convert it to the language and common
object file can be prepared with all the address resolution.
● The task of loader becomes simpler as it simply obeys the instruction
regarding where to place the object code to the main memory.
● The process of execution is efficient.
22
 Disadvantages of Absolute Loader

● In this scheme, it's the programmer's duty to adjust all the inter-segment
addresses and manually do the linking activity.
● For that, it is necessary for a programmer to know the memory
management.
● If at all any modification is done to some segment, the starting address of
immediate next segments may get changed.
● The programmer has to take care of this issue and he/she needs to update
the corresponding starting address on any modification in the source.

23
 Compile and Go Loader

● In this scheme, the architecture of memory is like, an assembler present in

memory.
● It resides in memory when we have a compile-and-go loading scheme.
● In another part of memory, there is an assembled source program.
● Assembled machine instruction is placed directly into their assigned memory
location.

24
 Working of Compile and Go Loader

● In this scheme, the source code goes into the translator line by line, and then
that single line of code loads into memory.
● Chunks of source code go into execution.
● Line-by-line code goes to the translator so there is no proper object code.
● Because of that, if the user runs the same source program, every line of code
will again be translated by a translator.
● So here re-translation happens.

25
 Working of Compile and Go Loader

● The source program goes through the translator (compiler/assembler).

● It consumes one part of the memory and the second part of the memory is
consumed by the assembler.
● The source program does not need that assembler but it is still there so this is
a waste of memory.

26
Working of Compile and Go Loader

27
 Subroutine Linkage

● Its a mechanism to call another subroutine in ALP.

● Example: A main program want to transfer to subroutine B. The programmer
in program A write a transfer instruction to subprogram B. The assembler
does not know the value of this symbol reference and will declare it as error
saying undefined symbol if a special mechanism is not provided.
● This mechanism is implemented with a relocating or a direct linking loader.

28
 Subroutine Linkage

● The assembler pseudo-opcode EXTERN followed by a list of symbols

indicate that these symbols are defined in other programs but referenced in
the present program.
● If symbol is defined in one program and referenced in other program then
pseudo opcode ENTRY followed by a list of symbols is used.
● Example:

29
 Subroutine Linkage

Example: ● In this Example SUBROUT is external

variable.
MAIN START ● It is refernced in this program but defined
EXTERN SUBROUT in other program.
------------ ● Load instruction loads address of that
------------ variable into register 15.
L 15=A(SUBROUT) ● BALR instruction branches to context of
BALR 14,15 register 15 ( address of SUBROUT) and
. leaves the next instruction in register 14.
.
END

30
 Relocation

● Program P uses instructions and data from set of absolute address instructions
or data addresses and occupy memory words with specific addresses.
● Such a program is called an address sensitive program.
● An address sensitive program executes correctly only if the start address of
the memory area allocated to it is as its translated origin.
● Program relocation is the process of modifying the address used in the
address sensitive instructions of a program such that the program can execute
correctly from the designated area of memory.

31
 Relocation

● Assembler decides whether an entity is absolute or relocatable.

● Absolute entities are address insensitive.
● Labels, symbols, literal addresses are relocatables.
● Object modules are relocatable programs.
● Self reloacting program can perform relocation on its own, For that two
provisions are given.
– A table of information that ahve address sensitive indtructions.
– Code to perform relocation. This is called relocating logic.

32
 Relocation

● A self relocating program can execute in any area of memory.

● To determine whether the result of address expression is either absolute or
relative, replace each term in address expression either by 0 if the term is for
absolute address and by 1 if the term is for a relative address.
● In the following table X, Y,Z, V, W are labels or symbols.
Address expression Relocation Attribute

X-Y absolute

X+Y-Z relative

X+7+V-W relative

33
 Relocating Loader

● To avoid possible reassembling of subroutines, when a single subroutine is

changed, and to perform task of relocation and linking for programmer,
relocating loader is introduced.
● BSS loader allows many procedure segments and one common data segment.
● The assembler assembles each procedure segment independently and passes
on to the loader the text and information as to relocation and intersegment
reference.

34
 Relocating Loader

● The assembler outputs object program and information about all other
programs it reference and relocation information.
● The assembler produces text which is prefixed by a transfer vector.
● Transfer vector consists of addresses containing names of the subroutines
referenced by the source program.
● Assembler provide loader with additional information as length of entire
program and length of transfer vector.

35
 Relocating Loader

● A loader loads transfer vector and text into core. Then loader load each
subroutine identified in transfer vector.
● Transfer vector is used to solve the program of linking and the program
length information is used to solve the problem of allocation.
● The four functions of loader alolcation, linking, relocation and loading all are
performed by BSS loader.
● The problem of relocation can be solved by relocation bits.

36
 Relocating Loader

Relocation bits
● The assembler associates a bit with each instruction.

● If this bit is 1 then corresponding address field must me relocated. Otherwies

not.

37
 Advantages and Disadvantages of Relocating Loader

Advantages
● It avoids reassembling of all subroutines, when a single subroutine changes.
● All four functions allocation, linking relocation and loading are performed by loader.
● Independant translation of each module.
Disadvantages
● Transfer vector are useful only for transfers and not suitable for loading and storing
erxtrenal data.
● Transfer vector increases the size of object program.
● BSS loader processes procedure segment but does not facilitate access to data
segments that can be shared. 38
 Direct Linking Loader
• The loader cannot have the direct access to the source code.
• The assembler should give the following information to the loader
i. The length of the object code segment
ii. The list of all the symbols which are not defined in the current segment but
can be used in the current segment.
Iii. The list of all the symbols which are defined in the current segment but can
be referred by the other segments.

39
 Direct Linking Loader

• USE table: stores the list of symbols which are not defined in the current
segment but can be used in the current segment.
• DEFINITION table: stores the list of symbols which are defined in the
current segment and can be referred by the other segments.
• There are 4 types of cards available in the direct linking loader. They are
⁃ ESD-External symbol dictionary
⁃ TXT-card
⁃ RLD-Relocation and linking dictionary
⁃ END-card
40
 Direct Linking Loader
i. ESD card: It contains information about all symbols that are defined in the
program but reference somewhere, It contains:
Reference number
Symbol name
Type Id
Relative location
Length
• There are again ESD cards classified into 3 types of mnemonics. They are:
i. SD [Segment Definition]: It refers to the segment definition
ii. LD: It refers to the local definition
iii. ER: it refers to the external reference they are used in the [EXTRN] pseudo
41
 Direct Linking Loader
iii. RLD Card:
• This card contains information about location in the program whose contexts
depends on the address at which the program is placed.
• In this we are used ‘+’ and ‘–‘sign, when we are using the ‘+’ sign then no
need of relocation, when we are using ‘-‘sign relocation is necessary.
• The format of RLD contains:
i. Reference number
ii. Symbol
iii. Flag
iv. Length
v. Relative location 42
 Design of Direct Linking Loader
We are taking PG1 and PG2 are two programs.
•The relative address and source code of above two programs is written in the
below.

43
SOURCE CARD REFERENCE RELATIVE ADDR PROGRAM STMT

1 0 P1 START

2 ENTRY RESULT

3 EXTERN P2

4 A 1,DATA

5 DC A(RESULT)

6 DC A(P2)

7 END

PROCEDURE P2

8 0 P2 START

9 ENTRY DATA

10 EXTERN RESULT

11 DC F 5

12 DC A(RESULT)

13 END

END 44
 Design of Direct Linking Loader
ESD Cards: In an ESD card, table contains information necessary to build the
external symbol dictionary or symbols table.
In the above source code the symbols are P1, P2, RESULT,DATA

SOURCE NAME TYPE ID RELATIVE LENGTH

CARD ADDR
REFERENCE
1 P1 SD 01 0 24

2 RESULT LD -- 12

3 P2 ER 02 --

45
 Design of Direct Linking Loader
TXT Cards:

SOURCE CARD RELATIVE CONTENTS OPERATION PERFORMED

REFERENCE ADDR

5 16 12 Address of Result

6 20 0 Address of P2 is unknown to to P1
so kept as 0.

46
 Design of Direct Linking Loader
RLD Cards:

SOURCE CARD ESD ID LENGTH FLAG (+ OR -) RELATIVE ADDRESS

REFERENCE

5 01 4 + 16

6 02 4 + 20

47
 ESD CARD FOR P2

SOURCE CARD NAME TYPE ID RELATIVE address

REFERENCE

8 P2 SD 01 0

9 DATA LD -- 16

10 RESUL ER O2 --
T

48
 TXTCARD

SOURCE RELAtive contents Operation Performed

CARD address
REFERENCE
11 16 5 Declared constant as 5

12 20 0 Address of RESULT is unknown to P2 so

kept as 0

49
 RLD CARD

SOURCE ESD ID LENGTH FLAG (+ OR -) RELATIVE ADDRESS

CARD
REFERE
NCE
12 02 4 + 20

50
 Pass1 database of Design of Direct Linking Loader
Specification of data structure:
i. Input object decks
ii. Initial Program Load Addresses [IPLA]: The IPLA supplied by the
programmer or operating system that specifies the address to load the first
segment.
iii. Program Load Address counter [PLA]: It is used to keep track of each
segments assigned location.
iv. Global External Symbol Table [GEST]: It is used to store each external
symbol and its corresponding assigned core address.
v. A copy of the input to be used later by pass2 51
 Pass2 database of Design of Direct Linking Loader
i. A copy of object program is input to pass2
ii. The Initial Program Load Address [IPLA]
iii. The Program Load Address counter [PLA]
iv. A table the Global External Symbol Table [GEST]
v. The Local External Symbol Array [LESA]: which is used to establish a
correspondence between the ESD ID numbers used on ESD and RLD cards and
the corresponding External symbols , Absolute address value.

52
 Pass1 Processing
we process SD LD from ESD card and prepare the GEST.
Let p1 is loaded at location 100 and P2 is loadfed at location 200 in the core.
The sample GEST is as shown below.
Symbol Assigned Core Addresses

“P1bbbbbb” 100

“RESULTS” 112

“P2bbbbbb” 200

“DATAbbbb” 216

53
 Pass2 Processing
LESA is created to establish connection between ID numbers on RLD card and
absolute core addresses. TXT card, RLD card and ER symbols from ESD card are
processed. Contents of LESA based on P1 are given below.
ID ASSIGNED CORE ADDR OF
Corresponding sYMBOLS
1 100

2 200

54
 Pass2 Processing
Actual CNTE

` ID ASSIGNED CORE ADDR OF

Corresponding sYMBOLS
1 100

2 200

55
 Dynamic Linking Loader
• used to allow several executing program to share one copy of a subroutine or
library.
• eg. runtime support routines for C could be stored in dynamic link library.
• A single copy of routine in this library could be loaded into the memory of the
computer.
• All C programs currently in execution could be linked to this one copy , instead
of linking a sepereate copy into each object program.
•

56
 Dynamic Linking Loader

It provides the ability to load the routine only when they are needed so lot of
time and memory is saved if subroutine are large with lots of external references.
• In dynamic linking loader is used to load the main main program.

57
 Steps in dyanamic linking and loading

-> the symbolic name of the routine in the program is used to make the load and
call service request to the operating system.
-> OS checks the internal tables to determine whether or not the routine is
already loaded.
-> control is then being passed from the os to the routine being called.
-> When the called subroutine completes its processing, the os then returns the
control of the program that issued this request.

58
 Advantages and Disadvantages

Advantages
-> No overhead is incured unless the procedure to be called or referenced is
actually used.
-> a further advantages is that the system can be dynamically configured.
Disadvantages
-> Considerable overhead and complexity incurved, due to the fact that we have
to postpone most of the binding process until execution time.

59