Linkers

Views:
 
     
 

Presentation Description

Linkers algorithm,relocation concepts with example

Comments

By: prasadme0875 (103 month(s) ago)

very fine

Presentation Transcript

Linkers : 

Linkers Neha Bhatt Lecturer, M.C.A Dept MITM

Introduction: : 

Introduction: Linker Loader Translator .Obj .exe Program execution Source program Translator translates source program to machine code and creates object file. Linker receives set of object files and links them solving external reference problems and creates ready to execute file.(which is a binary file). Loader loads this binary file to execution area for its execution

Important terminologies : : 

Important terminologies :

Relocation and linking concepts: : 

Relocation and linking concepts: Program relocation: Program relocation is the process of modifying the addresses used in the address sensitive instructions of a program such that it can execute correctly from the designated area of memory. Explanation: An address sensitive instruction is the one which uses an address in a form of absolute address(immediate address ) or address constants(data word which contains an address). Ex: Loop MOVE AX,A Loop and A both are address constants. If linker origin <>translated origin : relocation is done by linker If load origin <>linked origin relocation must be done by loader. If a program is created from multiple subprograms, all the subprograms have to be loaded at non-overlapping addresses. Relocation is the process of assigning load addresses to the various parts of the program, adjusting the code and data in the program to reflect the assigned addresses.

Relocation concepts: : 

Relocation concepts: Performing relocation: Relocation factor =l_origin –t_origin tsymb=t_origin+dsymb lsymb=l_origin+dsymb Lsymb=t_origin +relocation factor+dsymb =t_orgin +dsymb+relocation factor =tsymb+relocation factor IRR=Instructions requiring relocation. Ex: Let IRR for prog P has dispalcement(dsymb)=40,t_origin=500,l_origin=900 then Relocation factor=900-500=400 tsymb=500+40=540;lsymb=900+40=940 lsymb=540+400=940

Linking concepts: : 

Linking concepts: Linking: Linking is a process of binding an external reference to the correct link time address. Explanation: Computer programs typically comprise several parts or modules; all these parts/modules need not be contained within a single object file, and in such case refer to each other by means of symbols. Typically, an object file can contain three kinds of symbols: Publicly defined symbols, which allow it to be called by other modules , also called as public definition . Externally defined symbols(undefined symbols), which calls the other modules where these symbols are defined, also called as external reference. Local symbols, used internally within the object file to facilitate relocation.

Linking concepts: : 

Linking concepts: When a program comprises multiple object files, the linker combines these files into a unified executable program, resolving the symbol references. Symbol resolution: When a program is built from multiple subprograms, the references from one subprogram to another are made using symbols; a main program might use a square root routine called sqrt, and the math library defines sqrt. A linker resolves the symbol by noting the location assigned to sqrt in the library, and patching the caller's object code to so the call instruction refers to that location. In assembly public/External definitions of a symbol is done using following directives: ENTRY: Lists the public definition EXTRN: Lists the symbols to which external reference is made in the program unit.

Linking concepts: : 

Linking concepts: Example: Program unit P: START 500 EXTRN ALPHA,MAX 500 MOVER AX,ALPHA 501 ADD AX,05 502 STOP 503 Program unit Q: START 200 ENTRY ALPHA,MAX 200 MOVER AX,MAX 201 ALPHA DS 01 202 MAX DS 01 203 STOP 204 Let l_origin of P=900,size=40 t_orgin of P =500 Hence for program P relocation factor=900-500=400 Program P faces symbol resolution problem as it doesn’t know the actual displacements of Alpha and max as these are external definitions. We know t_origin of Q is 200 As alpha & max are publicly defined in Q their tsymb can be calculated as: tsymb of alpha=200+2=202 tsymb of max=200+3=203 Now lsymb for alpha & max(used in prog P) can obtained as: lsymb of alpha= l_origin+dsymb =900+42+2=942 Or lsymb= t_orgin +relocation factor+dsymb 500+400+42+2=942 Here we ought to add size of the program as external references are linked after actual code in memory.

Design of linker: : 

Design of linker: Input to linker is object files which is processed by linker to produce ready to execute file.

Design of linker: : 

Design of linker: Object module: It contains all information necessary to relocate and link the program. It consists of following elements: 1)Header:Contains translated origin ,size and execution start addtress of program. 2)Program:Contains the machine code corresponding to program. 3)RELOCTAB: Descibes IRR.It cntains single field:translated address. 4)LINKTAB(Symbol,Type,translated address):Contains information concerningpublic definitions. Type:PD/EXT

Design of linker: : 

Design of linker: Ex: Demo START 499 ENTRY A 499 EXTRN ALPHA,MAX 500 Loop MOVER AX,ALPHA 501 READ A 502 ADD AX,A 503 JMP loop 504 A DS 05 505 STOP 506 RELOCTAB LINKTAB Object module header

Design of linker:Relocation algorithm: : 

Design of linker:Relocation algorithm: 1.program_linked_origin:=<link origin> 2.For each object module a)t_origin:=translated origin of the object module. OM_size:=size of the object module; b)relocation_factor:= program_linked_origin - t_orgin; c)Read the m/c lang. prog. In work area; d)Read RELOCTAB of the object module e)For each entry in RELOCTAB i)Translated_addr:=Address in theRELOCTAB entry ii)Addr_in _work_area:=Addr_in _work_area+Translated_addr-t_orgin; iii)Add relocation_factor to the operand address in the word with the addr. in work area. f) program_linked_origin:= program_linked_origin+OM_size; Ex: Let addr in work area=300,Link origin=900,t_origin=500 ,size=42 then Relocation factor=900-500=400 I Addr_in _work_area=300+504-499=321 program_linked_origin=900+42=942

Relocation and linking : 

Relocation and linking After relocation link address of only address sensitive instructions are obtained. Using these addresses all codes except external references are relocated to link origin. In linking procedure address of publicly defined symbols and their link time addresses are stored in NTAB Using NTAB entries external reference are attached with obj module code in link area.

Design of linker:Linking algorithm: : 

Design of linker:Linking algorithm: 1.program_linked_origin:=<link origin> 2.For each object module a)t_origin:=translated origin of the object module. OM_size:=size of the object module; b)relocation_factor:= program_linked_origin - t_orgin; c)Read the m/c lang. prog. In work area; d)Read LINKTAB of the object module e)For each entry in LINKTAB with type=PD i)name:=symbol; linked_address:=translated_address+relocation factor; Enter(name,linked_address)in NTAB f)Enter(object module name,Prog_linked_origin)in NTAB g)Prog_linked_origin:=Prog_linked_origin+OM_size; 3.For each object module a)t_origin:=translated origin of the object module program_linked_origin:=load address from NTAB; b)For each LINKTAB entry with type=EXT i)Addr_in_work_area:=Addr of work area+Program_linked_origin-Link_origin+translated addr. –t_orgin; ii)Search symbol in NTAB and copy its linked address. Add this linked address to operand address in the word with the address with address_in_work_area.

Design of linker:Relocation algorithm: : 

Design of linker:Relocation algorithm: Ex: Sample2: START 200 ENTRY ALPHA,MAX 200 MOVER AX,MAX 201 ALPHA DS 01 202 MAX DS 01 203 STOP 204 Ex:Sample 1 START 499 ENTRY A 499 EXTRN ALPHA,MAX 500 Loop MOVER AX,ALPHA 501 READ A 502 ADD AX,A 503 JMP loop 504 A DS 05 505 STOP 506 Object module header

Design of linker: : 

Design of linker: RELOCTAB- sample1 LINKTAB-sample1 NTAB(After relocation & linking of both sample1 and sample2 modules)

Design of MS DOS Linker : 

Design of MS DOS Linker

MS DOS linker working : 

MS DOS linker working Works in two passes: Pass-1 :Relocation Pass-2:Linking It excepts object modules as set of several records these records are classified into 14 types depending on following criteria: Binary image External reference Public definitions Debugging information Miscellaneous information Main records used in algorithm are: THEADER,LNAMES, SEGDEF, EXTDEF,PUBDEF, LEDATA,FIXUPP, MODEND.

MS DOS linker working : 

MS DOS linker working Object record formats: THEADER LNAMES SEGDEF

Pass-1(First pass of linker) : 

Pass-1(First pass of linker) Linker command: LINKER<object module names>,<exe file>,<load origin>,<list of library files> Eg: LINKERalpha+beta+gama,Calculate,100050,pas.lib Aim of frist pass: To develop NTAB processing the information provided by object modules records. Information actually concerns about public definitions and segments. Develop NAMELIST listing names of Symbols of segments.

Pass-1(First pass of linker) : 

Pass-1(First pass of linker) 1.Prog_load_origin:=<load origin>; 2.Repeat step 3 for each object module to be linked. 3.Select an object module & process its object records. a)If LNAMES record ,enter the names in NAMELIST. b)If SEGDEF record i)i:=name index;segment_name:= NAMELIST[i]; Segment_addr:=start address in attributes; ii)If an absolute segment ,enter (segmentname,segment_addr)in NTAB. iii)If the segment is realocatable: -Align the address contained in Prog_load_origin on next word as indicated in attribute field. -Enter(segmentname,Prog_load_origin) in NTAB -Prog_load_origin:= Prog_load_origin+segmet length;

Slide 22: 

c)For each PUDEF record i)i:=base;segment_name:=NAMELIST[i];symbol:=name; ii)Segment_addr:=load_addr of segment_name in NTAB. iii)sym_addr:=segment_addr+offset; iv)Enter(symbol,sym_addr) in NTAB. Ex NAME FIRST Compute SEGMENT PARA1 Extern PHI,PSI ENTRY Alpha,Beta Alpha ------------------ MOV AX,PHI MOV AX,PSI Beta ---------------- Compute ENDS

Slide 23: 

NAME SECOND Part 2 SEGMENT PARA EXTRN Alpha,Beta,Gama ENTRY PHI,PSI PHI ------------------ Mov AX,PHI MOV AX,PSI PSI ---------------- Part 2 ENDS

Slide 24: 

]

Second pass: : 

Second pass: Constructs executable programs in work area moving data from LEDATA to appropriate parts of work area using segment index and data offset. First segment index is used to obtain the load origin of segment from NTAB. Add data offset to load origin gives load address of first byte in LEDATA. Then its address in work area is computed. Fixupps records are then processed to perform reallocation and linking. At the end .exe is written to current directory as<executable file>. Tables of second pass: NAMELIST, SEGTAB(segment name,load address) EXTTAB(external symbol,load address).It is built by processing og EXTDEF.

Pass-2(second pass of linker) : 

Pass-2(second pass of linker) 1.list_of_object modules:=obj modules named in LINKER command; 2.Repeat step 3until list_of_obj_modules is empty. 3.Select an object module & process its object records. a)If LNAMES record ,enter the names in NAMELIST. b)If SEGDEF record i)i:=name index;segment_name:= NAMELIST[i]; Enter(Segment_name,load adress from NTAB)in SEGTAB. c)If an EXTDEF record i)External_name:=name from EXTDEF record; ii)If external_name not found in NTAB -Locate an obj. module in library which contains external_name as segment/public definition. -Add name of object module to list_of_object_modules. -Perform first pass of LINKER.(autolinking) iii)Enter(external_name,load_addr from NTAB)inEXTTAB. d)If LEData record i)i:=segment index; d:=data_offset;

Pass-2(second pass of linker) : 

Pass-2(second pass of linker) ii)prog_link_orgin:=SEGTAB[i]->Load_addr; iii)address_in_work_area:= address of work_area +prog_load_origin-<loadorgin>+d; iv)Move data from LEDATA into the memory area starting at the address adress_in_work_area; e)If FIXUPP record i)f:=value of locat field; ii)fix_up_addr:=adress_in_work_area+f; iii)Perform required fix up using a load address from SEGTAB or EXTTAB abd the value of code in locat and fixdat. f)If MODEND record If start adress is specified,compute the corresponding load address and record it in the executable file being generated.

Slide 28: 

After processing FIRST NTAB

Slide 29: 

NAMELIST SEGTAB EXTTAB

Slide 30: 

After processing SECOND NTAB

Slide 31: 

NAMELIST SEGTAB EXTTAB

authorStream Live Help