CS代考 CMPUT 379 (E.S. Elmallah)

Static and Dynamic Linking and Loading
 Reference:
o Computer Organization and Design: The Hardware Software Interface, D. Patterson and J. Hennessy, 5/E, Sec. 2.12
Some Related Terms

Copyright By PowCoder代写 加微信 powcoder

Absolute Code
o requires loading at specified absolute addresses
CMPUT 379 (E.S. Elmallah)
Position Independent Code (PIC)
o Works when placed anywhere in memory. o How to generate?
• Use branch instructions (with PC-relative addresses)
• Access static data using the “offset + base register” addressing mode
• Use an extra level of indirection for every control transfer, load, or store outside the PIC area
CMPUT 379 (E.S. Elmallah)

Relocatable Code
o Can be relocated (to execute) anywhere o How to generate?
• Generate code + extra information to enable code and data relocation
CMPUT 379 (E.S. Elmallah)
Object Files (*.o) in Unix
Each file is a relocatable module. Sections: o Header
o Text segment:
• Code in the source file; may be unexecutable because of unresolved references
o Data segment:
• May be incomplete because of unresolved
references in other files o Relocation Information
• Identifies instructions and data words that depend on absolute addresses (need adjustment)
CMPUT 379 (E.S. Elmallah)

o Symbol Table
o Debugging information
• Which address corresponds to which source line?
Linker (or Link Editor)
o Combines object files to produce an executable
image (*.out) to be loaded in memory
• Determines memory locations that each module will occupy
• Resolves references among files
o Loads statically linked, or dynamically linked
executable files in memory for execution CMPUT 379 (E.S. Elmallah)
Linking Object Files
Example: two files
.global A,X .extern B
X: .word …
A: lw $a0,X
Note: global variables are referenced using the $gp register
CMPUT 379 (E.S. Elmallah)
.global B,Y .extern A
Y: .word …
B: sw $a0,Y

Input to the linker
header: procedure A, text size= 0x100, data size= 0x20
text segment: 0x[0] lw $a0, 0 ($gp) 0x[4] jal 0
data segment: 0x[0] (X)
// offset needs adjustment // offset needs adjustment
// value at label X
relocation Info: 0x[0] lw instruction requires X 0x[4] jal instruction requires B
symbol table:
CMPUT 379 (E.S. Elmallah)
header: procedure B, text size= 0x200, data size= 0x30
text segment: 0x[0] sw $a0, 0 ($gp) 0x[4] jal 0
data segment: 0x[0] (Y)
// offset needs adjustment // offset needs adjustment
// value at label Y
relocation Info: 0x[0] sw instruction requires Y 0x[4] jal instruction requires A
symbol table:
CMPUT 379 (E.S. Elmallah)

Output of linker:
o an executable image (to be loaded in memory),
o Text segment 0x[0040 0000], data segment 0x[1000 0000], $gp= 0x[1000 8000]
text segment:
data segment:
text segment size= 0x300, data segment size= 0x50
0x[0040 000] lw $a0, 0x8000 ($gp) 0x[0040 0004] jal 0x[0040 0100]
0x[0040 0100] sw $a1, 0x8020 ($gp) 0x[0040 0104] jal 0x[0040 000]
0x[1000 0000 ] (X) // value at label X 0x[1000 0020] (Y)
CMPUT 379 (E.S. Elmallah)
Steps to run “a.out”
o Read header to determine text segment size and data
segment size
o Obtain memory space for text and data segments
o Load “a.out” in memory
o Initialize registers (e.g., $sp, and $gp)
o Jump to a start-up routine that calls main()
o When main() returns, the start-up routine calls exit()
CMPUT 379 (E.S. Elmallah)

Dynamic Linking of Shared Libraries
A library (e.g., libc.a or libc.so) is a collection of relocatable files in a special archive format
o On Unix, we use the “ar” program
Static linking to a library produces a self- contained executable “a.out”
o Cons: “a.out”
• is relatively large
• does not use new versions of the library
CMPUT 379 (E.S. Elmallah)
Dynamic linking
o Library referenced by main (directly or indirectly) are
linked and loaded at runtime o How?
• Program and library routines keep extra information of nonlocal symbols
• The loader runs a dynamic linker that uses the extra information
CMPUT 379 (E.S. Elmallah)

// Main program with global variable X
extern void foo(); extern int Y;
void main() { …
foo (); X= … ; Y= … ; …
// A shared library routine compiled for dynamic linking
int Y; extern int X;
void foo() { …
foo (); X= … ; Y= … ; …
CMPUT 379 (E.S. Elmallah)
Compiler generates “linkage tables” for main() and foo()
$gp (main) address of foo when $gp (foo) loaded
Address of X when loaded
Address of Y when known
Linkage table of foo (used by foo)
address of X when known
address of Y when loaded
Linkage table of main (used by main)
CMPUT 379 (E.S. Elmallah)

Linkage table of foo …
Linkage table of main ….
Text segment foo
CMPUT 379 (E.S. Elmallah)
Basic dynamic loading
o All six parts: (main’s text, data, and linkage table) + (foo’s text, data, and linkage table) are loaded and linked at runtime
CMPUT 379 (E.S. Elmallah)

Dynamic lazy linking  Objective:
o avoid loading text and data segments that are never used in an execution
How (in our example)?
o Start by loading main’s text, data, and linkage table +
foo’s data segment (since it is referenced by main)
o Initially, foo’s address is not stored in main’s linkage table.
o Rather the address of foo refers to a “stub routine” created by the compiler and included in the main’s text segment:
CMPUT 379 (E.S. Elmallah)
• Load foo’s index in the library in a register
– e.g., foo is function number 100 in the library
• Save $ra
• Call the “lazy linker” of the library (linked to main at load time)
o The lazy linker:
• Loads foo’s text segment, linkage table, and all
referenced data segments
• Changes foo’s address in all loaded linkage tables
o Execute foo
o Return to original caller
CMPUT 379 (E.S. Elmallah)

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com