Unit-III-Loader & Linker - Sri Eshwar

System Software
Loaders & Linkers
Veningston .K
Department of CSE Government College of Technology, Coimbatore [email protected]
Loaders & Linkers
Outline
Basic loader functions Design of an Absolute Loader A Simple Bootstrap Loader Machine dependent loader features
Program Relocation Program Linking Algorithm and Data Structures for Linking Loader
Machine-independent loader features

Automatic Library Search Loader Options
Loader design options

Linkage Editors Dynamic Linking Bootstrap Loaders
24/August/2013
System Software - Sri Eshwar College of Engineering
Recap [1/3]
Machine architectures
Simplified Instructional Computer (SIC) SIC/XE [eXtra Equipment]
Assembler
Translate mnemonic operation codes to their machine language equivalents Assign machine addresses to symbolic labels used by the programmer Write the object program
24/August/2013
Recap [2/3]
Format of Object program
24/August/2013
Recap [3/3]
Object program contains translated instructions and data values from the source program, and specifies addresses in memory where these items are to be loaded
24/August/2013
Basic loader functions

Loading
Brings object program into memory
Relocation
Modifies the object program so that it can be loaded at an address different from the location originally specified
Linking
Combines two or more separate object programs and supplies information needed to allow references between them
Loader and linker may be a single system program

Loader: loading and relocation Linker: linking
24/August/2013
Linking Loader
6
Absolute loader
No linking and relocation needed All functions are accomplished in a single pass Records in object program perform
Header record
Check the Header record for program name, starting address, and length (available memory)
Text record
Bring the object program contained in the Text record to the indicated address
End record
Transfer control to the address specified in the End record to begin execution of the loaded program
24/August/2013
Loading of an absolute program [1/2]

Object program
24/August/2013
Loading of an absolute program [2/2]

Program loaded in memory
No text record indicates that the previous contents of these locations remain unchanged System Software - Sri Eshwar College of
24/August/2013 Engineering
Algorithm for an absolute loader
24/August/2013
10
Object Code Representation

Character form
Each byte of assembled code is given using its hexadecimal representation in character form Easy to read by human beings Inefficient in terms of space and execution time
Binary form
Each byte of object code is stored as a single byte in the object program Most machine store object programs in a binary form
Less space and loading time Not good for reading
24/August/2013
11
A simple bootstrap loader

Bootstrap Loader (usually in ROM)
When a computer is first tuned on or restarted, a special type of absolute loader, the bootstrap loader loads the first program (usually O.S.) to be run into memory
SIC bootstrap loader

The bootstrap itself begins at address 0 It loads the OS starting address 0x80 No header record, end record or control information The object code is loaded into consecutive bytes of memory starting at address 80 After loading the OS, the control is transferred to the instruction at address 80. Begins the execution of the program
24/August/2013
12
SIC bootstrap loader
24/August/2013
13
Algorithm for SIC/XE bootstrap loader
24/August/2013
14
Machine-Dependent Loader Feature

Merits of an absolute loader
Simple and efficient
limitation of an absolute loader

Programmer needs to specify the actual address at which it will be loaded into memory. It is difficult to run several programs concurrently, sharing memory between them. It is difficult to use subroutine libraries efficiently.
Solution
A more complex loader that provides
Program relocation Program linking
24/August/2013
15
(Recap) Program relocation

Why?
It is desirable to load and run several programs at the same time The system must be able to load programs into memory wherever there is room The exact starting address of the program is not known until load time It is not practical to plan program execution
(we do not know exactly when jobs will be submitted, exactly how long they will run)
24/August/2013
16
(Recap) Example of program relocation
24/August/2013
17

Absolute program
Program with starting address specified at assembly time The address may be invalid if the program is loaded into somewhere else.
Example
24/August/2013
18

The only parts of the program that require modification at load time are those that specify direct addresses The rest of the instructions need not be modified
Not a memory address (immediate addressing) PC-relative, Base-relative
From the object program, it is not possible to distinguish the address and constant
The assembler must keep some information to tell the loader The object program that contains the modification record is called a relocatable program
24/August/2013
19
(Recap) The way to solve the relocation problem

For an address label, its address is assigned relative to the start of the program (START 0) Produce a Modification record to store the starting location and the length of the address field to be modified. The command for the loader must also be a part of the object program
24/August/2013
20
(Recap) Modification record

One modification record for each address to be modified The length is stored in half-bytes (4 bits) The starting location is the location of the byte containing the leftmost bits of the address field to be modified. If the field contains an odd number of halfbytes, the starting location begins in the middle of the first byte.
24/August/2013
21
(Recap) Modification record
24/August/2013
22
(Recap) Relocatable Object Program
24/August/2013
23
Relocation
Loaders that allow for program relocation are called relocating loaders or relative loaders. Efficient sharing of the machine requires that we write relocatable programs instead of absolute ones. The way relocation is implemented in a loader is also dependent upon machine characteristics. Linking is not a machine-dependent function
24/August/2013
24
Relocation
Two methods for specifying relocation as part of the object program Modification records
For a small number of relocations required when relative or immediate addressing modes are extensively used
Relocation bits
For a large number of relocations required when only direct addressing mode can be used in a machine with fixed instruction format (e.g., the standard SIC machine)
24/August/2013
25
Object program with relocation by modification records
24/August/2013
26
Relocatable program for SIC
24/August/2013
27
24/August/2013
28
24/August/2013
29
Review on Relocatable program for SIC

The standard SIC machine does not use relative addressing (PC-relative, Base-relative) All instructions except RSUB in this program need relocation [require 31 Modification records] Too many modification records The modification record scheme is a convenient means for specifying program relocation; however, it is not well suited for use with all machine architectures
24/August/2013
30
Relocation Bits
If there are many addresses needed to be modified, it is more efficient to use a relocation bit, instead of a Modification record, to specify every relocation.
When the instruction format is fixed There is a relocation bit for each word of the object program Relocation bits are put together into a bit mask If the relocation bit corresponding to a word of object code is set to 1, the programs starting address will be added to this word when the program is relocated
24/August/2013
31
Relocation Bits
24/August/2013
32
Relocation Bits
A bit value of 0 indicates that no modification is necessary [e.g. data constants and JSUB] If a text record contains fewer than 12 words of object code, the bits corresponding to unused words are set to 0 A new Text record is created for proper alignment Relocation bits are generated by the Assembler and used by the Loader.
24/August/2013
33
Program linking
Goal
Resolve the problems with EXTREF and EXTDEF from different control sections
A program is a logical entity that combines all of the related control sections. Control sections could be assembled together, or they could be assembled independently of one another. Control sections are to be linked, relocated, and loaded by loaders.
24/August/2013
34
(Recap)Expression
The assemblers allow the use of expressions as operand The assembler evaluates the expressions and produces a single operand address or value Expressions consist of
Operator
+,-,*,/ (division is usually defined to produce an integer result)
Individual terms
Constants User-defined symbols Special terms, e.g. *, the current value of LOCCTR
Examples
MAXLEN STAB EQU RESB BUFEND-BUFFER (6+3+2)*MAXENTRIES
24/August/2013
35
(Recap)Relocation Problem in Expressions

Values of terms can be
Absolute (independent of program location)
Constants
Relative (to the beginning of the program)

Address labels * (value of LOCCTR)
Expressions can be
Absolute
Only absolute terms
MAXLEN EQU 1000
Relative terms in pairs with opposite signs for each Pair [independent on program starting address]
MAXLEN EQU BUFEND-BUFFER
Relative
All the relative terms except one can be paired as described in absolute. The remaining unpaired relative term must have a positive sign.
STAB
24/August/2013
EQU
OPTAB + (BUFEND BUFFER)

36
(Recap) Program blocks vs. Control sections

Program blocks (Assembler directive: USE)
Segments of code that are rearranged within a single object program unit
Control sections (Assembler directive: CSECT)

Segments of code that are translated into independent object program units
24/August/2013
37
(Recap) Control Sections and Program Linking

Control sections
can be loaded and relocated independently of the other control sections are most often used for subroutines or other logical subdivisions of a program the programmer can assemble, load, and manipulate each of these control sections separately because of this, there should be some means for linking control sections together
24/August/2013
38
(Recap) External Definition and Reference

Instructions in one control section may need to refer to instructions or data located in another section External definition
EXTDEF name [, name]
EXTDEF names symbols that are defined in this control section and may be used by other sections E.g. EXTDEF BUFFER, BUFEND, LENGTH
External reference
EXTREF name [,name]
EXTREF names symbols that are used in this control section and are defined elsewhere E.g. EXTREF RDREC, WRREC
To reference an external symbol, extended format instruction is needed

24/August/2013
39
(Recap) Records for Object Program

The assembler must include information in the object program that will cause the loader to insert proper values where they are required
24/August/2013
40
(Recap) Records for Object Program
24/August/2013
41
Program linking
Example
Program for Linking and Relocation Use modification records for both relocation and linking
address constant external reference
24/August/2013
42
Program for Linking and Relocation [1/3]
24/August/2013
43
24/August/2013
44
24/August/2013
45
About the assembly program

3 control sections: PROGA, PROGB, PROGC List of items: LISTA, LISTB, LISTC Set of references to external symbols
Instruction operands: REF1, REF2, REF3 Values of data words: REF4 through REF8
These programs are given to emphasize the relationship between the relocation and linking process.
24/August/2013
46
From the loader point of view

Programmer think of a program as a logical entity that combines all of the related control sections However, from the loader point of view, there is no such thing as a program. There are only control sections that are to be linked, relocated, and loaded. The loader do not need to know which control sections were assembled at the same time
24/August/2013
47
Object programs [1/3]
24/August/2013
48
24/August/2013
49
24/August/2013
50
About the object program

Local reference is assembled using PC-relative instruction with no relocation or linking required Modification record instructing the loader to add the value of the external symbol to this address field when the program is linked
24/August/2013
51
Note
The general approach taken is for the assembler to evaluate as much of the expression as it can The remaining terms are passed on to the loader via modification records
24/August/2013
52
Example - 1
Consider REF4, the assembler for PROGA can evaluate all of the expression in REF4 except for the value of LISTC. This results in an initial value of 000014 and one Modification record
24/August/2013
53
Example - 2
Consider REF4, in PROGB contains no terms that can be evaluated by the assembler The object code therefore contains an initial value of 000000 and three Modification record
24/August/2013
54
Example - 3
Consider REF4, for PROGC assembler can supply the value of LISTC relative to the beginning or the program (but not the actual address which is not known until the program is loaded) The initial value of this data word contains the relative address of LISTC 000030 Modification records instruct the loader to add the beginning address of the program (i.e. the value of PROGC), to add the value of ENDA, and to subtract the value of LISTA
24/August/2013
55
Inference from the example 1, 2 & 3

The expression in REF4 represents
a simple external reference for PROGA A more complicated external reference for PROGB A combination of relocation and external references for PROGC
24/August/2013
56
Exercise
To work through references REF5 through REF8 by yourself to be sure that you have understood how the object code and modification records are generated
24/August/2013
57
Programs after linking and loading
24/August/2013
58
Inference from the previous Figure

Note that each of REF4 through REF8 has resulted (after relocation and linking is performed) in the same value in each of the three programs, Since the same source expression appeared in each program
24/August/2013
59
Example
The value for reference REF4 in PROGA is located at address 4054 (the beginning address of PROGA + 0054, the relative address of REF4 within PROGA) Next slide shows how this value is computed?
24/August/2013
60
Relocation and linking operations performed on REF4
24/August/2013
61
Note
For the reference that are instruction operands, the calculated values after loading do not always appear to be equal This is because there is an additional address calculation step involved for PC-relative or Base-relative instructions.
24/August/2013
62
Algorithm and data structure for a linking loader

Programmer do not need to worry about how these calculations are actually performed by the loader The algorithm and data structures does
24/August/2013
63
Algorithm and data structure for a linking loader

Considerations by SIC/XE:
Most instructions uses relative addressing; no relocation is necessary Modification records are used in this type of machine
A linking loader usually makes two passes over its input

Because some external symbols are processed before read
24/August/2013
64
Two passes linking loader

Two Passes Logic
Pass 1: assign addresses to all external symbols Pass 2: perform the actual loading, relocation, and linking
24/August/2013
65
Linking loader - Pass 1 [1/3]

Assign address to all external symbols
Only processes Header Record and Define Record Builds an external symbol table (ESTTAB)
its name its address in which control section the symbol is defined
Program Load Address (PROGADDR)

The beginning address in memory where the linked program is to be loaded (supplied by OS).
Control Section Address (CSADDR)

The starting address assigned to the control section currently being scanned by the loader. CSADDR is added to all relative addresses within the control section
24/August/2013
66

Add symbol to ESTAB
Control section name: (name, CSADDR) ESTAB
Get control section name from H record If the first control section
CSADDR = PROGADDR
When E record is encountered, read the next control section

CSADDR = CSADDR + CSLTH (known from H record)
EXTDEF: (name, CSADDR + value in the record) ESTAB

Get EXTDEF from D record
24/August/2013
67

At the end of Pass 1: ESTAB contains all external symbols defined in the set of control sections together with the address assigned to each Print the load map if necessary (optional) useful in program debugging
24/August/2013
68
Linking loader - Pass 1 algorithm
24/August/2013
69
Linking loader - Pass 2

Perform the actual loading, relocation, and linking
Only processes Text Record and Modification Record Get address of external symbol from ESTAB When read T record
Moving object code to the specified address
When read M record

(+/-) EXTREF in M to be used for modification is looked up in ESTAB This value is added/subtracted from the indicated location in memory
Last step: transfer control to the address in E

If more than one control section specifies a transfer address: loader arbitrarily uses the last one If no control section contains a transfer address: transfer control to the first instruction (PROGADDR)
24/August/2013
70
Linking loader - Pass 2 algorithm
24/August/2013
71
Linking loader To improve efficiency

We can make the linking loader algorithm more efficient by
Assigning a reference number to each external symbol referred to in a control section
01: control section name 02~: external reference symbols
This reference number is used (instead of the symbol name) in Modification records Avoids multiple searches of ESTAB for the same symbol during the loading of a control section.
Search of ESTAB for each external symbol can be performed once and the result is stored in a table indexed by the reference number. The values for code modification can then be obtained by simply indexing into the table.
24/August/2013
72
Examples of Using Reference Numbers [1/3]
24/August/2013
73
The reference numbers are underlined in the Refer and modification records
24/August/2013
74
24/August/2013
75
Machine-Independent Loader Feature

Automatic Library Search
Automatic library search for handling external references
Allows a programmer to use subroutines from one or more libraries as they are needed during linking The subroutines called by the program being loaded are automatically fetched from the library, linked with the main program, and loaded.
Solution

24/August/2013
A flag for each symbol in ESTAB (defined/undefined) When add a symbol on R record to ESTAB, set it as undefined If a symbol on D record is found, set is as defined At the end of Pass 1, search the library for undefined symbol If all libraries are searched and some undefined symbol (unresolved external references) still remains, output error a message
76
Discussions of Automatic Library Search

The presented linking loader allows the programmer to override the standard subroutines by supplying his/her own routines. Directory
The loader searches for the subroutines by scanning the Define records for all of the object programs. (inefficient) It can be more efficient by searching a directory that gives the name and address of each routine.
The same techniques applies equally well to the resolution of external references to data items
24/August/2013
77
Loader Options
Users can specify options that modify the standard processing of the loader. Many loaders have a special command language that is used to specify options
Written in a separate input file Embedded in the primary input stream between object programs Included in source program Specified in job control language
24/August/2013
78
Loader Options - Command language [1/2]

Selection of alternative sources of input
INCLUDE program-name(library-name)
Direct the loader to read the designated object program from a library
Deletion of external symbols

DELETE csect-name
Instruct the loader to delete the named control sections from the set of programs being loaded
Change the external symbols

CHANGE name1, name2
Cause the external symbol name1 to be changed to name2 wherever it appears in the program
24/August/2013
79
Loader Options - Command language [2/2]

Automatic inclusion of library routines
LIBRARY My_LIB
Specify alternative libraries to be Searched User-specified libraries are normally searched before the standard system libraries.
NOCALL LIB_name
Specify the external reference name are to remain unresolved. If it is known that some external reference is not to be performed in an execution
NOCALL STDDEV, PLOT

24/August/2013
80
Loader Design Options

Loaders
Linkage editor
Linking before loading
Dynamic linking
Linking at the execution time
Bootstrap loader
24/August/2013
81
Linkage Editors
Difference between a linkage editor and a linking loader
Linking loader
Performs all linking and relocation operations, including automatic library search, and loads the linked program into memory for execution.
Linkage editor
Produces a linked version of the program, which is normally written to a file or library for later execution.
A simple relocating loader (one pass) can be used to load the program into memory for execution. The linkage editor performs relocation of all control sections relative to the start of the linked program. The only object code modification necessary is the addition of an actual load address to relative values within the program
24/August/2013
82
Compare between linking loader and linkage editor

Linking loader
Suitable when a program is reassembled for nearly every execution
In a program development and testing Environment When a program is used so infrequently that it is not worthwhile to store the assembled and linked version.
Linkage editor
Suitable when a program is to be executed many times without being reassembled because resolution of external references and library searching are only performed once.
24/August/2013
83
Linking loader vs. linkage editor
24/August/2013
84
Additional Functions of Linkage Editors

Replacement of subroutines in the linked program Construction of a package for subroutines generally used together
There are a large number of cross-references between these subroutines due to their closely related functions.
Specification of external references not to be resolved by automatic library search

Can avoid multiple storage of common libraries in programs. Need a linking loader to combine the common libraries at execution time.
24/August/2013
85
Dynamic Linking
Comparison
Linkage editors perform linking operations before the program is loaded for execution Linking loaders perform linking operations at load time Dynamic linking (dynamic loading, load on call) perform linking at execution time
Delayed Binding
Avoid the necessity of loading the entire library for each execution, i.e. load the routines only when they are needed Allow several executing programs to share one copy of a subroutine or library (Dynamic Link Library (DLL))
24/August/2013
86
Dynamic Linking
O.S. services request of dynamic linking
Dynamic loader is one part of the OS Instead of executing a JSUB instruction that refers to an external symbol, the program makes a load-and-call service request to the OS
Example Figures
When call a routine, pass routine name as parameter to O.S. (a) If routine is not loaded, O.S. loads it from library and pass the control to the routine (b and c) When the called routine completes it processing, it returns to the caller (O.S.) (d) When call a routine and the routine is still in memory, O.S. simply passes the control to the routine (e)
24/August/2013
87
Example of Dynamic Linking [1/2]
24/August/2013
88
Example of Dynamic Linking [2/2]
24/August/2013
89
Bootstrap Loaders
How is the loader itself loaded into memory?
An absolute loader program is permanently resident in a read-only memory (ROM) Copy absolute loader in ROM into RAM for execution (optional) Read a fixed-length record from some device into memory at a fixed location. After the read operation, control is automatically transferred to the address in memory
24/August/2013
90
Discussions & Queries
24/August/2013
91

Unit-III-Loader & Linker - Sri Eshwar

Uploaded by

Copyright:

Available Formats

Unit-III-Loader & Linker - Sri Eshwar

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit-III-Loader & Linker - Sri Eshwar

Uploaded by

Copyright:

Available Formats

System Software

Loaders & Linkers

Loaders & Linkers

Machine-independent loader features

Loader design options

System Software - Sri Eshwar College of Engineering

System Software - Sri Eshwar College of Engineering

System Software - Sri Eshwar College of Engineering

Basic loader functions

Loader and linker may be a single system program

Loading of an absolute program [1/2]

System Software - Sri Eshwar College of Engineering

Loading of an absolute program [2/2]

Algorithm for an absolute loader

System Software - Sri Eshwar College of Engineering

Object Code Representation

A simple bootstrap loader

SIC bootstrap loader

SIC bootstrap loader

System Software - Sri Eshwar College of Engineering

Algorithm for SIC/XE bootstrap loader

System Software - Sri Eshwar College of Engineering

Machine-Dependent Loader Feature

limitation of an absolute loader

(Recap) Program relocation

(Recap) Example of program relocation

System Software - Sri Eshwar College of Engineering

(Recap) Program relocation

System Software - Sri Eshwar College of Engineering

(Recap) Program relocation

(Recap) The way to solve the relocation problem

System Software - Sri Eshwar College of Engineering

(Recap) Modification record

(Recap) Modification record

System Software - Sri Eshwar College of Engineering

(Recap) Relocatable Object Program

System Software - Sri Eshwar College of Engineering

Object program with relocation by modification records

System Software - Sri Eshwar College of Engineering

Relocatable program for SIC

System Software - Sri Eshwar College of Engineering

Relocatable program for SIC

System Software - Sri Eshwar College of Engineering

Relocatable program for SIC

System Software - Sri Eshwar College of Engineering

Review on Relocatable program for SIC

System Software - Sri Eshwar College of Engineering

System Software - Sri Eshwar College of Engineering

System Software - Sri Eshwar College of Engineering

(Recap)Relocation Problem in Expressions

Relative (to the beginning of the program)

OPTAB + (BUFEND BUFFER)

System Software - Sri Eshwar College of Engineering

(Recap) Program blocks vs. Control sections

Control sections (Assembler directive: CSECT)

System Software - Sri Eshwar College of Engineering

(Recap) Control Sections and Program Linking

(Recap) External Definition and Reference

To reference an external symbol, extended format instruction is needed

(Recap) Records for Object Program