Memory Management Background: Address Binding & Linking
Example
Main.c:
main( )
{
static float x, val;
extern float sin( ); extern printf( ), scanf( )
printf(“Type number: ”); scanf(“%f”, &x);
val = sin(x);
printf(“Sine is %f”, val);
}
Math.c:
float sin(float x) {
static float temp1, temp2, result;
– Calculate Sine –
return result; }
1
Example (cont)
l Main.c uses externally defined sin() and C library function calls
l printf() l scanf()
l How does this program get compiled and linked?
2
Tasks of a Linker
l Read in object files produced by the compiler l Produce a self-sufficient object file (a.out)
l Involves
l segment relocation l address translation
3
Back to the Example
l Do the main/sin example with the following segment sizes
l Main: code 420, data 42
l Math: code 1600, data 12
l Library: code 1230, data 148
l Output: code 3250, data 202
l In reality segment starts on a page (4 Kbytes) boundary
4
Memory Layout – Division of Responsibility
l Compiler: generates object file
l Information is incomplete
l Each file may refer to symbols defined in other files
l Linker: puts everything together
l Creates one object file that is complete l No references outside this file (usually)
5
Division of Responsibility (cont)
lOS
l Allow several different processes to share physical
memory
l Provide ways of dynamically allocating more physical memory
6
What could the compiler not do?
l Compiler does not know final memory layout
l It assumes everything in .o starts at address zero
l For each .o file, compiler puts information in the symbol table to tell the linker how to rearrange outside references safely/efficiently
l For exported functions, absolute jumps, etc l Linker needs to rearrange segments
l What makes rearrangement tricky? l Addresses!
7
What couldn’t the compiler do? (cont)
l Compiler does not know all the references l e.g. addresses of functions / variables defined
in other files
l Where it does not know, it just puts a zero, and leaves a comment (relocation info) for the linker to fix things up
l These are called cross references
8
Components of Object File
l Header
l Two segments
l Code segment and data segment
l OS adds empty heap/stack segment while loading
l Size and address of each segment
l Address of a segment is the address where the segment begins
9
Components of Object File (cont)
l Symbol table
l Information about stuff defined in this module
l Used for getting from the name of a thing (subroutine/variable) to the thing itself
l Relocation information
l Information about addresses in this module linker
should fix
l External references (e.g. lib call)
l Internal references (e.g. absolute jumps)
l Additional information for debugger
10
Linker functionality
l Three functions of a linker
l Collect all the pieces of a program
l Figure out new memory organization
l Combine like segments
l Does the ordering matter? (spatial locality for cache)
l Touch-up addresses
l The result is a runnable object file (e.g. a.out)
11
Linker – a closer look
l Linker can shuffle segments around at will, but cannot rearrange information within a segment
12
Linker requires at least two passes
l Pass 1: decide how to arrange memory l Pass 2: address touch-up
13
Pass 1 – Segment Relocation
l Pass 1 assigns input segment locations to fill-up output segments
l Read and adjust symbol table information
l Read relocation info to see what additional stuff from libraries is required
14
Pass 2 – Address translation
l In pass 2, linker reads segment and relocation information from files, fixes up addresses, and writes a new object file
l Relocation information is crucial for this part
15
Putting It Together
l Pass 1:
l Read symbol table, relocation table
l Rearrange segments, adjust symbol table
l Pass 2:
l Read segments and relocation information l Touch-up addresses
l Write new object file
16
Dynamic linking
l Static linking – each lib copied into each binary l Dynamic linking:
l Instead of system call wrapper code, a stub that finds lib code in memory, or loads it if it is not present
l Pros:
l all procs can share copy (shared libraries) l Standard C library
l live updates
17
Dynamic loading
l Program can call dynamic linker via l dlopen()
l library is loaded at running time
l Pros:
l More flexibility — A running program can l create a new program
l invoke the compiler
l invoke the linker
l load it!
18
Memory Usage Classification
l Memory used to store information that can be used in various ways
l Some possible classifications
l Role in programming language l Changeability
l Address vs. data
l Binding time
19
Role in Programming Language
l Instructions
l Specify the operations to be performed
on the operands l Variables
l Store the information that changes as program runs
l Constants
l Used as operands but never change
20
Changeability
l Read-only
l Example: code, constants
l Read and write
l Example: Variables
21
Address vs. Data
l Need to distinguish between addresses and data
l Why?
l Addresses need to be modified if the memory is re-arranged
22
Binding Time
l When is the space allocated?
l Compile-time, link-time, or load-time
l Static: arrangement determined once and for all
l Dynamic: arrangement cannot be determined until runtime, and may change
l malloc( ), free( )
23
Classification – summary
l Classifications overlap
l Variables may be static or dynamic
l Code may be read-only or read and write l Read-only: Solaris
l Read and write: DOS
l So what is this all about?
l What does memory look like when a process is running?
24
Memory Layout
l Memory divided into segments
l Code (called text in Unix terminology) l Data
l Stack
l Why different segments?
l To enforce classification
l e.g. code and data treated differently at hardware level
25
The big picture
l a.out needs address space for
l text seg, data seg, and (hypothetical) heap, stack
l A running process needs phy. memory for l text seg, data seg, heap, stack
l But no way of knowing where in phy mem at l Programming time, compile time, linking time
l Best way out?
l Make agreement to divide responsibility
l Assume address starts at 0 at prog/compile/link time l OS needs to work hard at loading/runing time
27
Big picture (cont)
l OS deals with physical memory
l Loading
l Sharing physical memory between processes l Dynamic memory allocation
28
Connecting the dots
main.o math.o
main.c math.c
compiler
a.out
memory management
loader
Logical memory
Logical memory & Physical memory
OS
arch
Instruction execution
linker
Load a.out to mem Manage mem for proc
29
Loading
a.out file
Header Text
Data
Process
Text size
Data size
Text segment
Data
Heap Stack
30
Dynamic memory allocation during program execution
l Stack: for procedure calls
l Heap: for malloc()
l Both dynamically growing/shrinking
l Assumption for now:
l Heap and stack are fixed size
l OS has to worry about loading 4 segments per process:
l Text l Data l Heap l stack
31
1. Simple uniprogramming:
Single segment (code, data, stack heap) per process
Physical memory
OS
Segment 1 address 0
32
Simple uniprogramming: Single segment per process
l Highest memory holds OS
l Process is allocated memory starting at 0, up to the
OS area
l When loading a process, just bring it in at 0
l virtual address == physical address! l Examples:
l early batch monitor which ran only one job at a time l if the job wrecks the OS, reboot OS
l 1st generation PCs operated in a similar fashion l Pros / Cons?
33
Multiprogramming
l Want to let several processes coexist in main memory
34
Issues in sharing main memory
l Transparency:
l Processes should not know memory is shared
l Run regardless of the number/locations of processes l Safety:
l Processes cannot corrupt each other l Efficiency:
l Both CPU and memory utilization shouldn’t be degraded badly by sharing
35
2. Simple multiprogramming
With static software memory relocation, no protection, 1 segment per process:
l Highest memory holds OS
l Processes allocated memory starting at 0, up to
the OS area
l When a process is loaded, relocate it so that it can run in its allocated memory area
l How? (use symble table and relocation info) l Analogy to linking?
36
Simple multiprogramming:
Single segment per process, static relocation
OS
Segment 2 Segment 1
37
37
Simple multiprogramming:
Single segment per process, static relocation
OS
Segment 2
Segment 1 completed Segment 3
Segment 4?
38
38
Simple multiprogramming:
Single segment per process, static relocation
l four drawbacks
1. No protection
2. Low utilization — Cannot relocate dynamically l Binary is fixed (after loading)
l Cannot do anything about holes
3. No sharing — Single segment per process
l Cannot share part of process address space (e.g. text)
4. Entire address space needs to fit in mem
l Need to swap whole, very expensive!
39
39
What else can we do?
l Already tried
l Compile time / linking time l Loading time
l Let us try execution time!
40
40