CS代考 Operating Systems - CSCI 402

Operating Systems – CSCI 402
3.4 Linking & Loading
Static Linking & Loading
Shared Libraries
29
321 0
Copyright ý . Systems – CSCI 402
Remember This?
eip
args
local variables
saved registers
ebp
main:
pushl %ebp
movl %esp, %ebp
pushl %esi
pushl %edi
subl $8, %esp
…
pushl $1
movl -12(%ebp), %eax
pushl %eax
call sub
addl $8, %esp
movl %eax, -16(%ebp)
…
addl $8, %esp
movl $0, %eax
popl %edi
popl %esi
movl %ebp, %esp
popl %ebp
ret
set up stack frame
push args
pop args; get result
set return value and restore frame
esp
int main() {
int i;
int a;
…
i = sub(a, 1);
…
return(0);
}
30
321 0
Copyright ý . Systems – CSCI 402
Something Simpler
local variables (none)
saved registers (none)
ebp
eip
args
int main(int argc,
char *[]) {
return(argc);
}
main:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %eax
movl %ebp, %esp
popl %ebp
ret
Does location matter?
stack frame of main()
set up stack frame
set return value and restore frame
esp
31
321 0
Copyright ý . Cheng

}
Operating Systems – CSCI 402
Something Simpler
local variables (none)
saved registers (none)
ebp
eip
args
int main(int argc,
char *[]) {
return(argc);
main:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %eax
movl %ebp, %esp
popl %ebp
ret
Does location matter?
stack frame of main()
set up stack frame
set return value and restore frame
ebp, esp
35
321 0
Copyright ý . Systems – CSCI 402
Something Simpler
local variables (none)
saved registers (none)
ebp
eip
args
int main(int argc,
char *[]) {
return(argc);
}
main:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %eax
movl %ebp, %esp
popl %ebp
ret
Does location matter?
stack frame of main()
set up stack frame
set return value and restore frame
esp
36
321 0
Copyright ý . Cheng

local variables (none)
saved registers (none)
ebp
eip
args
int main(int argc,
char *[]) {
return(argc);
}
main:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %eax
movl %ebp, %esp
popl %ebp
ret
Does location matter?
stack frame of main()
set up stack frame
set return value and restore frame
esp
Something Simpler
Operating Systems – CSCI 402
if everything can be accessed relative to the frame pointer, then you don¡¯t need to know the actual address of an object
just use relative-addresses to access variables
the code is also location-independent Copyright ý . Cheng
321 0
37

Why does it matter here?
need to put the address of X into aX what is the address of X?
when do you know?
remember, both X and aX are in the data segment who would put the actual value into aX?
Operating Systems – CSCI 402
int X = 6;
int *aX = &X;
int main( ) {
void subr(int);
int y = X;
subr(y);
return(0);
}
void subr(int i) {
printf(“i = %d\n”, i);
}
Location Matters …
also need to put the address of subr into main() Copyright ý . Cheng
321 0
38

compiler figure out how many bytes each object is assign them temporary locations
linker figures out where each object is and lays out the entire address space
functions, global variables, and more
Relocation
modify internal references in memory depending on where module is expected to be loaded
one of the exec system calls loads a program into memory everything is laid out carefully in memory
modules requiring relocation are said to be relocatable the act of modifying such a module to resolve these references is called relocation
the program that performs relocation is called a linker
textbook is wrong
321 0
Operating Systems – CSCI 402
Done in two steps
Coping
39
Copyright ý . Systems – CSCI 402
main functions of a linker 1) relocation
2) symbol resolution
find unresolved symbols and figure out how to resolve them
A loader loads a program into memory
“unfolds” a program from disk into memory and “transfer control” to it (i.e., “executes” it)
a “relocating loader” may perform additional relocation
but that¡¯s dynamic linking
40
321 0
Copyright ý . Slight Revision
Operating Systems – CSCI 402
extern int X;
int *aX = &X;
int main( ) {
void subr(int);
int y = *aX;
subr(y);
return(0);
}
#include
int X;
void subr(int i) {
printf(“i = %d\n”, i);
}
subr.c
% gcc -o prog main.c subr.c
main.c
main.c is compiled into main.o
subr.c is compiled into subr.o
ld is then invoked to combine them into prog
ld knows where to find printf()
prog can be loaded into memory through one of the exec system calls
relocatable modules
321 0
41
Copyright ý . Slight Revision
Operating Systems – CSCI 402
extern int X;
int *aX = &X;
int main( ) {
void subr(int);
int y = *aX;
subr(y);
return(0);
}
#include
int X;
void subr(int i) {
printf(“i = %d\n”, i);
}
main.c
subr.c
% gcc -o prog main.c subr.c
how does ld decides what needs to be done?
main.c contains undefined references to X and subr()
instructions for doing this are provided in main.o
later on, when the actual locations for these are determined, ld will modify them when main.o is copied into prog
321 0
42
Copyright ý . Slight Revision
Operating Systems – CSCI 402
extern int X;
int *aX = &X;
int main( ) {
void subr(int);
int y = *aX;
subr(y);
return(0);
}
#include
int X;
void subr(int i) {
printf(“i = %d\n”, i);
}
main.c
subr.c
% gcc -o prog main.c subr.c
main.o must contains a list of external symbols, along with their types, and instructions for updating this code
43
321 0
Copyright ý . Cheng

main.c
A header file typically contains declaration/definition of data structures declaration of exported symbols
subr.c
Operating Systems – CSCI 402
Can Also Use A Header File
extern int X;
void subr(int);
#include “subr.c”;
int *aX = &X;
int main( ) {
int y = *aX;
subr(y);
return(0);
}
subr.h
#include
int X;
void subr(int i) {
printf(“i = %d\n”, i);
}
44
321 0
Copyright ý . Systems – CSCI 402
Offset Op Arg
main.s
0: .data ; what follows is initialized data
0: .globl aX ; aX is global: it may be used
; by others
0: aX:
0: .long X
4:
0: .text ; offset restarts; what follows is
; text (read-only code)
0: .globl main
0: main:
0: pushl %ebp ; save the frame pointer
1: movl %esp,%ebp ; point to current frame extern int X;
3: subl $4,%esp ; make space for y on stack int *aX = &X;
6: movl aX,%eax ; put contents of X into eax
11: movl (%eax),%eax ; put *X into %eax
int main( ) { 13: movl %eax,-4(%ebp) ; store *aX into y
16: pushl -4(%ebp) ; push
19: call subr
y
void subr(int); onto isntayc=k *aX;
subr(y);
return(0);
24: addl $4,%esp ; remove y from stack
27: movl $0,%eax ; set return value to 0
31: movl %ebp, %esp ; restore stack pointer
33: popl %ebp ; pop frame pointer
35: ret
321 0
}
45
Copyright ý . Cheng

0: .data ; what follows is initialized data
0: .globl aX ; aX is global: it may be used
Operating Systems – CSCI 402
Offset Op Arg
main.s
; by others
0: aX:
0: .long X
4:
0: .text ; offset restarts; what follows is
; text (read-only code)
0: .globl main
0: main:
0: pushl %ebp ; save the frame pointer
offset got restarted because
segments are relocatable
1: movl %esp,%ebp ; point to current frame extern int X;
3: subl $4,%esp ; make space for y on stack int *aX = &X;
6: movl aX,%eax ; put contents of X into eax
11: movl (%eax),%eax ; put *X into %eax
int main( ) { 13: movl %eax,-4(%ebp) ; store *aX into y
16: pushl -4(%ebp) ; push
19: call subr
y
void subr(int); onto isntayc=k *aX;
subr(y);
return(0);
24: addl $4,%esp ; remove y from stack
27: movl $0,%eax ; set return value to 0
31: movl %ebp, %esp ; restore stack pointer
33: popl %ebp ; pop frame pointer
35: ret
321 0
}
48
Copyright ý . Op Arg
main.s
Operating Systems – CSCI 402
0: .data ; what follows is initialized data
0: .globl aX ; aX is global: it may be used
0: aX:
0: .long X
4:
i.e., can be referenced by other modules
; by others
.global directive means that the symbol mentioned is defined here and is exported
0: .text ; offset restarts; what follows is
; text (read-only code)
aX and main are global 0: pushl %ebp ; save the frame pointer
0: .globl main
0: main:
1: movl %esp,%ebp ; point to current frame extern int X;
3: subl $4,%esp ; make space for y on stack int *aX = &X;
6: movl aX,%eax ; put contents of X into eax
11: movl (%eax),%eax ; put *X into %eax
int main( ) { 13: movl %eax,-4(%ebp) ; store *aX into y
16: pushl -4(%ebp) ; push
19: call subr
y
void subr(int); onto isntayc=k *aX;
subr(y);
return(0);
24: addl $4,%esp ; remove y from stack
27: movl $0,%eax ; set return value to 0
31: movl %ebp, %esp ; restore stack pointer
33: popl %ebp ; pop frame pointer
35: ret
321 0
}
49
Copyright ý . Cheng

0: .data ; what follows is initialized data
0: .globl aX ; aX is global: it may be used
; by others
0: aX:
0: .long X
4:
0: .text ; offset restarts; what follows is
; text (read-only code)
0: .globl main
0: main:
0: pushl %ebp ; save the frame pointer
Operating Systems – CSCI 402
Offset Op Arg
main.s
these 3 places require
relocation
1: movl %esp,%ebp ; point to current frame extern int X;
3: subl $4,%esp ; make space for y on stack int *aX = &X;
6: movl aX,%eax ; put contents of X into eax
11: movl (%eax),%eax ; put *X into %eax
int main( ) { 13: movl %eax,-4(%ebp) ; store *aX into y
16: pushl -4(%ebp) ; push
19: call subr
y
void subr(int); onto isntayc=k *aX;
subr(y);
return(0);
24: addl $4,%esp ; remove y from stack
27: movl $0,%eax ; set return value to 0
31: movl %ebp, %esp ; restore stack pointer
33: popl %ebp ; pop frame pointer
35: ret
321 0
}
51
Copyright ý . Op Arg
main.s
Operating Systems – CSCI 402
0: .data ; what follows is initialized data
0: .globl aX ; aX is global: it may be used
0: aX:
0: .long X
4:
what¡¯s stored at offset 20 is not the absolute address of subr, but a relative address
; by others
this call is a PC-relative call
0: .text ; offset restarts; what follows is
; text (read-only code)
0: .globl main
0: main:
0: pushl %ebp ; save the frame pointer
this is just how x86 works
1: movl %esp,%ebp ; point to current frame extern int X;
3: subl $4,%esp ; make space for y on stack int *aX = &X;
6: movl aX,%eax ; put contents of X into eax
11: movl (%eax),%eax ; put *X into %eax
int main( ) { 13: movl %eax,-4(%ebp) ; store *aX into y
16: pushl -4(%ebp) ; push
19: call subr
y
void subr(int); onto isntayc=k *aX;
subr(y);
return(0);
24: addl $4,%esp ; remove y from stack
27: movl $0,%eax ; set return value to 0
31: movl %ebp, %esp ; restore stack pointer
33: popl %ebp ; pop frame pointer
35: ret
321 0
}
52
Copyright ý . Systems – CSCI 402
Offset Op Arg
subr.s
0: .data ; what follows is initialized data
0: printfarg:
0: .string “i = %d\n”
8:
0: .comm X,4 ; 4 bytes in BSS is required
; for global X
4:
0: .text ; offset restarts; what follows is
; text (read-only code)
0: .globl subr
0: subr:
0: pushl %ebp ; save the frame pointer #include
1: movl %esp, %ebp ; point to current frame int X;
3: pushl 8(%ebp) ; push i onto stack
6: pushl $printfarg ; push address of string
11: call printf }
16: addl $8, %esp ; pop arguments from stack 19: movl %ebp, %esp ; restore stack pointer 21: popl %ebp ; pop frame pointer
23: ret
void subr(int i) { ; onto stack
printf(“i = %d\n”, i);
53
321 0
Copyright ý . Op Arg
subr.s
; text (read-only code)
Operating Systems – CSCI 402
0: .data ; what follows is initialized data
0: printfarg:
0: .string “i = %d\n”
8:
this is how you create a string constant
0: .comm X,4 ; 4 bytes in BSS is required
; for global X
0: .text ; offset restarts; what follows is
can “live” somewhere else
4:
0: .globl subr
0: subr:
and local to this module
this one is 8 bytes long
(since it¡¯s not global)
0: pushl %ebp ; save the frame pointer #include
1: movl %esp, %ebp ; point to current frame int X;
3: pushl 8(%ebp) ; push i onto stack
6: pushl $printfarg ; push address of string
11: call printf }
16: addl $8, %esp ; pop arguments from stack 19: movl %ebp, %esp ; restore stack pointer 21: popl %ebp ; pop frame pointer
23: ret
void subr(int i) { ; onto stack
printf(“i = %d\n”, i);
54
321 0
Copyright ý . Op Arg
subr.s
; text (read-only code)
Operating Systems – CSCI 402
0: .data ; what follows is initialized data
0: printfarg:
0: .string “i = %d\n”
8:
this is how you create a string constant
0: .comm X,4 ; 4 bytes in BSS is required
; for global X
0: .text ; offset restarts; what follows is
can “live” somewhere else
it is used here
4:
0: .globl subr
0: subr:
and local to this module
this one is 8 bytes long
(since it¡¯s not global)
0: pushl %ebp ; save the frame pointer #include
1: movl %esp, %ebp ; point to current frame int X;
3: pushl 8(%ebp) ; push i onto stack
6: pushl $printfarg ; push address of string
11: call printf }
16: addl $8, %esp ; pop arguments from stack 19: movl %ebp, %esp ; restore stack pointer 21: popl %ebp ; pop frame pointer
23: ret
void subr(int i) { ; onto stack
printf(“i = %d\n”, i);
55
321 0
Copyright ý . Op Arg
subr.s
; text (read-only code)
Operating Systems – CSCI 402
0: .data ; what follows is initialized data
0: printfarg:
0: .string “i = %d\n”
8:
mentioned is defined
here and is exported
0: .comm X,4 ; 4 bytes in BSS is required
; for global X
0: .text ; offset restarts; what follows is
4:
0: .globl subr
0: subr:
.comm directive also
4 bytes is required in the bss segment for this global variable
means that the symbol
0: pushl %ebp ; save the frame pointer #include
1: movl %esp, %ebp ; point to current frame int X;
3: pushl 8(%ebp) ; push i onto stack
6: pushl $printfarg ; push address of string
11: call printf }
16: addl $8, %esp ; pop arguments from stack 19: movl %ebp, %esp ; restore stack pointer 21: popl %ebp ; pop frame pointer
23: ret
void subr(int i) { ; onto stack
printf(“i = %d\n”, i);
56
321 0
Copyright ý . Cheng

0: .data ; what follows is initialized data
0: printfarg:
Operating Systems – CSCI 402
Offset Op Arg
subr.s
0: .string “i = %d\n”
8:
0: .comm X,4 ; 4 bytes in BSS is required
; for global X
4:
0: .text ; offset restarts; what follows is
; text (read-only code)
0: .globl subr
0: subr:
relocation is required for printf and printfarg
0: pushl %ebp ; save the frame pointer #include
1: movl %esp, %ebp ; point to current frame int X;
3: pushl 8(%ebp) ; push i onto stack
6: pushl $printfarg ; push address of string
11: call printf }
16: addl $8, %esp ; pop arguments from stack 19: movl %ebp, %esp ; restore stack pointer 21: popl %ebp ; pop frame pointer
23: ret
void subr(int i) { ; onto stack
printf(“i = %d\n”, i);
58
321 0
Copyright ý . Systems – CSCI 402
Object Files
An object file describes what¡¯s in the data, bss, and text segments in separate sections
Along with each section is a list of:
global symbols
undefined symbols instructions for relocation
these instructions indicate
which locations within the section must be modified which symbol¡¯s value is used to modify the location
a symbol¡¯s value is the address that is ultimately determined for it
typically, this address is added to the location being modified
To inspect an object file on Unix
nm – list symbols from object files
objdump – display information from object files
59
321 0
Copyright ý . Systems – CSCI 402
subr.o
Data:
Size: 8
Contents: “i = %d\n”
bss:
Size: 4
Global: X, offset 0
Text:
Size: 24
Global: subr, offset 0
Undefined: printf
Relocation:
offset 7, size 4, value: addr of printfarg
offset 12, size 4, value: PC-relative addr of
printf
Contents: [machine instructions]
No tool can generate exactly the above printout
60
321 0
Copyright ý . Systems – CSCI 402
subr.s
.data ; what follows is initialized data printfarg: relocation is required for:
Offset Op Arg
0: 0: 0: 8: 0:
4: 0:
0:
.string “i = %d\n”
.comm X,4 ; 4 bytes in BSS is required
; for global X
#include .text ; offset restarts; what follows is
printfarg at offset 7 printf at offset 12
0: subr:
.globl subr
void subr(int i) {
printf(“i = %d\n”, i);
int X; ; text (read-only code)
0: pushl %ebp ; save the frame pointer
1: movl %esp, %ebp ; point to current frame
3: pushl 8(%ebp) ; push i onto stack
6: pushl $printfarg ; push address of string
; onto stack
11: call printf
16: addl $8, %esp ; pop arguments from stack
19: movl %ebp, %esp ; restore stack pointer
21: popl %ebp ; pop frame pointer
23: ret
}
61
321 0
Copyright ý . Cheng

subr.o
Data:
Size: 8
Contents: “i = %d\n”
bss:
Size: 4
Global: X, offset 0
Text:
Size: 24
Global: subr, offset 0
Undefined: printf
Relocation:
relocation is required for: printfarg at offset 7 printf at offset 12
#include
int X;
void subr(int i) {
printf(“i = %d\n”, i);
offset 7, size 4, value: addr of printfarg
offset 12, size 4, value: PC-relative addr of
printf
Contents: [machine instructions]
}
Operating Systems – CSCI 402
62
321 0
Copyright ý . Cheng

subr.o
Data:
Size: 8
Contents: “i = %d\n”
bss:
Size: 4
Global: X, offset 0
Text:
Size: 24
Global: subr, offset 0
Undefined: printf
Relocation:
Xandsubrareexported needed in main.o
#include
int X;
void subr(int i) {
printf(“i = %d\n”, i);
offset 7, size 4, value: addr of printfarg
offset 12, size 4, value: PC-relative addr of
printf
Contents: [machine instructions]
}
Operating Systems – CSCI 402
63
321 0
Copyright ý . Cheng

0: .data ; what follows is initialized data 0: .globl aX ; aX is global: ithesmea2yplabces ruemseaidned
Operating Systems – CSCI 402
Offset Op Arg
main.s
0: aX:
0: .long X
4:
; by others
unresolved
0: .text ; offset restarts; what follows is extern int X;
0: .globl main
0: main:
int *aX = &X;
int main( ) {
; text (read-only code)
0: pushl %ebp ; save the frame pointer
void subr(int);
1: movl %esp,%ebp ; point to current frame int y = *aX;
3: subl $4,%esp ; make space for y on stack subr(y);
6: movl aX,%eax ; put contentsroetfurXn(0i)n;to eax }
11: movl (%eax),%eax ; put *X into %eax
13: movl %eax,-4(%ebp) ; store *aX into y
16: pushl -4(%ebp) ; push y onto stack
19: call subr
24: addl $4,%esp ; remove y from stack
27: movl $0,%eax ; set return value to 0
31: movl %ebp, %esp ; restore stack pointer
33: popl %ebp ; pop frame pointer
35: ret
321 0
64
Copyright ý . : Size: 4
these 2 places remained
bss: Size: 0
Text:
Size: 36
Global: main, offset 0
Undefined: subr
Relocation:
extern int X;
int *aX = &X;
int main( ) {
void subr(int);
int y = *aX;
subr(y);
return(0);
}
offset 7, size 4, value: addr of aX
offset 20, size 4, value: PC-relative
addr of subr
Contents: [machine instructions]
Operating Systems – CSCI 402
main.o
Global: aX, offset 0
Undefined: X
Relocation: offset 0, size 4, value: addr of X
Contents: 0x00000000
unresolved
they are noted in main.o
65
321 0
Copyright ý . : Size: 8
printfremainedunresolved
subr.o
Operating Systems – CSCI 402
Contents: “i = %d\n”
bss: Size: 4
Global: X, offset 0
Text:
Size: 24
Global: subr, offset 0
Undefined: printf
Relocation:
#include
int X;
void subr(int i) {
printf(“i = %d\n”, i);
offset 7, size 4, value: addr of printfarg
offset 12, size 4, value: PC-relative addr of
printf
Contents: [machine instructions]
}
66
321 0
Copyright ý . Cheng

printf.o
Data:
Size: 1024 assume that printf.o looks
offset 211, value: addr of StandardFiles
offset 723, value: PC-relative addr of write
Contents: [machine instructions]
Operating Systems – CSCI 402
Global: StandardFiles
Contents: …
bss:
Size: 256
Text:
Size: 12000
Global: printf, offset 100
…
Undefined: write
Relocation:
like this
write is unresolved
67
321 0
Copyright ý . Cheng

bss: Size: 4
Global: errno, offset 0
Text:
Size: 16
Contents: [machine
instructions]
Operating Systems – CSCI 402
write.o
Data:
Size: 0 and write.o looks like this
68
321 0
Copyright ý . Systems – CSCI 402
Data: Size: 0
bss: Size: 0
Text:
Size: 36
Undefined: main
Relocation:
offset 21, value: main
Contents: [machine
instructions]
every C program contains a startup routine that is called first
it calls main()
if main() returns, it calls exit()
our example is incomplete
startup function
69
321 0
Copyright ý . Cheng

this is how ld might set things up
ld lays out the address space
ld allocates memory in pages (typically 4KB each)
main does not start at location 0
first “page” is typically made inaccessible so that
references to null pointers will fail (get SIGSEG)
321 0
Operating Systems – CSCI 402
Text
main 4096
subr 4132
printf 4156
write 16156
startup 16172
Data
aX 16384
printfargs 16388
StandardFiles 16396
BSS
X 17420
errno 17424
prog
70
Copyright ý .
main 4096
subr 4132
printf 4156
write 16156
startup 16172
R/O
Operating Systems – CSCI 402
prog
Data aX
printfarg can be modified by the application
is that okay?
where else would you put it?
who decides?
16384
printfargs 16388
StandardFiles 16396
BSS
X 17420
errno 17424
due to the use of “pages”, the data segment needs to start at a page boundary (i.e., multiple of page size)
this way, the text segment can be made read-only while the data and bss segments made read-write
here we assume 4KB pages (therefore, pages start at
4096, 8192, 12288, 16384, etc.)
321 0
R/W
71
Copyright ý . Systems – CSCI 402
Page Protection & Virtual Memory Basics
A process has, say, a 32-bit address space
that¡¯s 4GB of memory
our prog process, when it starts, only needs about 16KB for text+data+bss (plus more for stack)
allocating 4GB of physical memory will be a huge waste
72
321 0
Copyright ý . Cheng

“address translation” done in hardware some advantages:
page protection
only allocate needed physical memory pages
a lot more to come in Ch 7
321 0
Operating Systems – CSCI 402
Page Protection & Virtual Memory Basics
A process has, say, a 32-bit address space
that¡¯s 4GB of memory
our prog process, when it starts, only needs about 16KB for text+data+bss (plus more for stack)
allocating 4GB of physical memory will be a huge waste
Solution: indirection
use page table to map virtual to physical addresses
a page table is a kernel data structure, used by the CPU
OS allocates pages of physical memory using the Buddy System
a page is 4KB in many systems
a page corresponds to physical memory that can be located (or “mapped”) anywhere in virtual memory
73
Copyright ý . Systems – CSCI 402
Page Protection & Virtual Memory Basics
Text
main 4096
subr 4132
printf 4156
write 16156
startup 16172
Data
aX 16384
printfargs 16388
StandardFiles 16396
BSS
X 17420
errno 17424
ask buddy system to allocate these pages
Page Table
Start
Access
Physical Addr
0
–
–
4096
R
8192
R
12288
R
16384
R/W
#
0 1 2 3 4
Copyright ý . Page
Physical Page
Physical Page
Physical Page
74
321 0

Related Posts