UNIT - 5

Linkers & Loaders

Q1) Explain Schematic of Program Execution?

A1)

Few Terminologies:

•Translation Time (or Translated) Address: Address assigned by the translator.

•Linked Address: Address assigned by the linker.

•Load Time (or Load) Address: Address assigned by the loader.

•Translated Origin: Address of the origin assumed by the translator. This is the address specified by the programmer in an ORIGIN statement.

•Linked Origin: Address of the origin assigned by the linker while producing a binary program.

•Load Origin: Address of the origin assigned by the loader while loading the program for execution.

Origin may need to be changed:

•The linked and load origins may differ from translated origin.

•Reason?

–Same set of translated addresses may have been used by different object modules of the program. These results to conflict in memory allocation.

–OS may require that a program should execute from specific area of memory. This may require change in its origin, thus changing execution start address and symbol addresses.

•Thus, require changes in origin by linker and loader.

Q2) Explain Program Relocation?

A2)

Address Sensitive Program:

•AA –Set of Absolute Addresses, may be instruction address or data address.

•AA ≠ ф; means instruction or data occupy memory words with specific address.

•Such a program is called address sensitive program which contains:

1. Address Sensitive Instruction: an instruction which contains address aiЄAA.

2. Address Constant: a data word which contains an address aiЄAA.

•Important: Address Sensitive Program P can execute correctly only if the start address of the memory area allocated to it is the same as its translated origin.

Start Address == Translation Address

•Thus, to execute correctly from any memory area, address used in each address sensitive instruction of P must be ‘corrected’.

•Def: Program Relocation: Is the process of modifying the address used in the address sensitive instructions such that the program can execute correctly from the designated area of memory.

•Linker performs relocation if

–Linked Origin ≠ Translated Origin

•Loader performs relocation if

–Load Origin ≠ Linked Origin

•In general: Linker always performs relocation, whereas some loaders do not.

•Absolute loaders do not perform relocation, then

–Load Origin = Linked Origin

–Thus, Load Origin and Linked Origin are used interchangeably.

Q3) Explain Performing Relocation and IRR: Instruction Requiring Relocation?

A3)

IRR: Instruction Requiring Relocation

•It’s a set of instructions that perform relocation in program p.

•Steps: –Calculate Relocation Factor (RF)

–Add it to Translation Time Address (es) for every instruction which is member of IIR.

•Eg: relocation factor = 900 -500 = 400

IRR contains translation addresses 540 & 538 (instruction: read A)

Address is changed to 540 + 400 = 940 and538 + 400 = 938.

Q4) Explain in detail Linking?

A4)

•AP is an Application Program consisting of a Set of Program units SP = { Pi }.

•A program unit Pi interacts with another program unit Pjusing instructions & addresses of Pj.

•For this it must have:

–Public Definition: a symbol pub_symb defined in program unit which may be referenced in other program.

–External Reference: a reference to a symbol ext_symb which is not defined in program unit containing the reference.

•Who will handle these two things?

EXTRN & ENTRY statements:

•The ENTRY statement lists the public definition of program unit.

–i.e. it list those symbols defined in program unit which may be referenced in other program units.

•The EXTRN statement list the symbols to which external references are made in the program unit.

•Eg:

–TOTAL is ENTRY statement. (public definition)

–MAX and ALPHA are EXTRN statements (external reference)

–Assembler don’t know address of EXTRN symb and so it puts 0’s address field of instruction wherever these symb are found.

–What if we don’t refer these varwith EXTRN stmts?

–Assembler gives errors.–Thus; requirement arises for resolving external references.

Resolving External Reference:

•Before AP (application program) executes, every external reference should be bound to correct link time address.

•Who will do this binding?

–Here comes Linker into the picture.

•Def: Linking: Linking is the process of binding an external reference to correct link time address.

•External reference is said to be unresolved until linking is performed and resolved once linking is completed.

•Linking is performed for the eg defined in pg. no 223 and the Q program unit defined as follows:

Example: Linked with Program Unit Q

ALPHA is external reference in that example which is linked with above given unit.

Q5) Explain in detail Binary Programs?

A5)

•Is a machine language program comprising set of program units SP such that for all PiЄSP,

–1. Pirelocatedat link origin.

–2. Linking is performed for each external referencein Pi.

•Linker Command:linker <link origin> <object module names>[, <execution start address> ]

•Linker converts object module into-> the set of program units (SP) into-> a binary program.

•If link address = load address, loader simply loads binary program into appropriate memory area for execution.

Object Module:

•Object Module(OM) contains all the information necessary to relocate and link the program with other programs.

•OM consist of four components:

–1. Header: Contains translated origin, size and execution start address of P.

–2. Program: Contains machine language program corresponding P.

–3. Relocation Table: (RELOCTAB) describing IRRp (Instruction Requiring Relocation). Each entry contains field: ‘Translated Address’ -of address sensitive instruction.

–4. Linking Table: (LINKTAB) contains information concerning public definition and external reference.

Has three fields:

•Symbol: symbolic name

•Type: PD/EXT i.e public definition or external reference

•Translated Address: If PD, address of first memory word allocated. If EXT, address of memory word containing reference of symbol.

Example:

•For previously given assembly program, object module contains following information:

•1. Translated Origin: 500, Size:42,Exe. Strt. Add=500.

•2. Machine Language Instructions

•3. Relocation table:

•4. Linking table:

•LOOP is not here asit is not PD.

Q6) Explain DESIGN OF LINKER?

A6)

•What influence relocation requirement of a program?

•Ans: Addressing Structure of Computer System.

•How to reduce relocation requirement of a program?

•Ans: By using segmented addressing structure.

•JUMP avoids use of absolute address; hence instruction is no more address sensitive.

•Thus, no relocation is needed.

•Effective Operand Address would be calculated considering starting address as 2000 would be <CS> + 0196 = 2196 (which is corrected address)

•Lets take example to understand it more clearly.

Example:

•Code written in assembly language for Intel 8088.

•ASSUME a statement declares segment register CS and DS for memory addressing.

•So, all memory addressing is performed using suitable displacement of their contents.

•Translation time address of A is 0196.

•In statement 16, reference of A due to JMP statement makes displacement of 196 from the content of CS register.

•Hence avoids usage of absolute addressing. Thus, instruction is not address sensitive. Displacement->avoids usage of absolute address->not address sensitive instruction.

•As DS is loaded with execution time address of DATA_HERE, reference to B would be automatically relocated to correct address.

•Thus, Use of segment register reduces relocation requirement but doesn’t eliminate it.

•Inter Segment Calls & Jumps are handled in similar way.

•Relocation is more involved in case of intra segment jumps assembled in FAR format.

•Linker computes both:–Segment Base Address–Offset of External Symbol

•Thus, no reduction in linking requirements.

Q7) What is Relocation Algorithm?

A7)

1. program_linked_origin:=<link origin> from Linker command;

2. For each object module

(a) t_origin:= translated origin of object module;OM_size:= size of object module;

(b) relocation_factor:= program_linked_origin–t_origin;

(c) Read the machine language program in work_area;

(d) Read RELOCTAB of object module.

(e) For each entry in RELOCTAB

(i) Translated_addr:= address in RELOCTAB entry;

(ii) address_in_work_area:= address of work_area+ translated_address–t_origin;

(iii) Add relocation_factorto the operand address in the word with the address ‘address_in_work_area’.

(f) Program_linked_origin:= program_linked_origin+ OM_Size.

Example:

•Let address of work_area= 300.

•While relocating OM, relocation factor = 400.

•For the first RELOCTAB entry, address_in_work_area= 300+500-500=300.

•This word contains the instruction for READ A.

•It is reallocated by adding 400 to operand address in it.

•For the second RELOCTAB entry, address_in_work_area=300+538-500=338.

•The instruction in this word is similarly relocated by adding 400 to the operand address in it.

Q8) What are the Linking Requirements?

A8)

•In FORTRAN all program units are translated separately.

•Hence, all sub program calls and common variable reference require linking.

•Programs are nested in main program.

•Procedure reference do not require linking, they can be handled using relocation.

•Build in functions requires linking.

•Linker processes all object modules being linked & builds a table of all public definition & load time address.

•Name Table (NTAB)

– (a) Symbol: Symbol Name for external reference or object module.

–(b) Linked Address: For public definition contains link_address. For object module contains link_origin.

•Most information in NTAB is derived from LINKTAB entries with type=PD.

Q9) Write an Algorithm: Program Linking?

A9)

1.program_linked_origin:= <link origin> from linker command.

2.For each object module

(a)t_origin:= translated origin of object module. OM_size:= size of the object module;

(b)Relocation_factor:= program_linked_origin–t_origin.

(c)Read the machine language program in work_area.

(d)Read LINKTAB of the object module.

(e)For each LINKTAB entry with type = PDname:= symbol;linked_address:= translated_address+ relocation_factor;enter(name,linked_address) in NTAB.

(f) Enter (object module name, program_linked_origin) in NTAB.

(g) program_linked_origin:= program_linked_origin+ OM_size;

3. for each object module

(a) t_origin:= translated origin of the object module.

(b) For each LINKTAB entry with type=EXT

(i) address_in_work_area:

= address of work_area+ program_linked_origin–<link_origin> + translated address –t_origin;

(ii) Search symbol in NTAB and copy itslinked address.

 Add the linked address to the operand address in the word with the address address_in_work_area.

Example:

•While linking program P and program Q with linked_origin=900, NTAB contains following information:

•Work_area= 300.

•When LINKTAB of alpha is processed during linking, address_in_work_area:= 300 + 900 -900 + 518 –500. i.e318.

•Hence linked address of ALPHA is 973, is copied from NTAB entry of ALPHA and added to word in address 318.

Q10) Explain SELF RELOCATING PROGRAMS?

A10)

•Types:

–Non Re-locatable Programs

–Re-locatable Programs

–Self Re-locating Programs

•1. Non-Re-locatable Programs:

–It cannot be executed in any memory area other than area starting on its translated origin.

–Has address sensitive programs.

–Lack information concerning address sensitive instruction

–Eg. Hand coded machine language program.

•2. Re-locatable Programs:

–It can be processed to relocate it into desired data area of memory.

–Eg: Object Module.

•3. Self-Relocating Programs:

–It can perform relocation of its own address sensitive instruction.

–Consist of:

•A table of Information (for address sensitive prg)

•Relocating logic–Self re-locating program can execute in any area of memory.

–As load address is different for each execution, good for time sharing systems.