Today’s Big Adventure!Linking– how to name and refer to things that don’t exist yet– how to merge separate name spaces into a cohesive whole!Readings– man elf on SysV/Linux/Solaris, man a.out on *BSD– run “nm” or “objdump” on a few .o and a.out files.– (or “otool” [OS X] or “readelf” [Stanford])f.cgccf.sasc.cgccc.sasf.oc.olda.outLinking as our first naming system!Naming = very deep theme that comes up everywhere– Naming system: maps names to values!Examples:– Linking: Where is printf? How to refer to it? How to deal with synonyms? What if it doesn’t exist– Virtual memory address (name) resolved to physical address (value) using page table – file systems: translating file and directory names to disk locations, organizing names so you can navigate, … – mit.edu resolved to 18.7.22.69 using DNS tablestreet names: translating (elk, pine, …) vs (1st, 2nd, …) to actual location– your name resolved to grade (value) using spreadsheet Why use Linking as a naming example?!Closely related to *loading* a program and creating a new process/address space!Modern systems use dynamic linking and resolve references at runtime (with caching for speed)!Shared libraries are an important optimization to reduce memory footprint and increase flexibility/patchability!Good for any systems programmer to understand!!You will get to modify the Pintos loader for code sharing/lazy allocation in project #3!3Perspectives on information in memory!Programming language view:– instructions: specify operations to perform– variables: operands that can change over time– constants: operands that never change!Changeability view (for sharing):– read only: code, constants (1 copy for all processes)– read and write: variables (each process gets own copy)!Addresses versus data– addresses used to locate something: if you move it, must update address– examples: linkers, garbage collectors, changing apartment!Binding time: when is a value determined/computed? – Early to late: compile time, link time, load time, runtimeadd r1, r2, 1How is a process specified?!Executable file: the linker/OS interface. – What is code? What is data? – Where should they live? !Linker builds ex from object files:codedataint a;foo: retcode=110 data=8, ... “foo.o”foo: call 0 ret bar: retl: “hello world\n”0foo: 0: Tbar: 40: t4: printf40Header: code/data size, symtab offsetObject code: instructions and data gen’d by compiler Symbol table: external defs (exported objects in file) external refs (global syms used in file)How is a process created? !On Unix systems, read by “loader” – reads all code/data segs into buffer cache; maps code (read only) and initialized data (r/w) into address space– fakes process state to look like switched out !Big optimization fun:– Zero-initialized data does not need to be read in.– Demand load: wait until code used before get from disk– Copies of same program running? Share code– Multiple programs use same routines: share code (harder)ldloaderCacheCompile time runtimeCS140 - Summer 2008 - Handout #8What does a process look like? (Unix)!Process address space divided into “segments”– text (code), data, heap (dynamic data), and stack– Why? (1) different allocation patterns; (2) separate code/dataheapstack codeinitialized dataaddress 2^n-1address >= 0Who builds what?!Heap: constructed and layout by allocator (malloc)– compiler, linker not involved other than saying where it can start– namespace constructed dynamically and managed by programmer (names stored in pointers, and organized using data structures)!Stack: alloc dynamic (proc call), layout by compiler– names are relative off of stack pointer– managed by compiler (alloc on proc entry, dealloc on exit)– linker not involved because name space entirely local: compiler has enough information to build it.!Global data/code: allocation static (compiler), layout (linker)– compiler emits them and can form symbolic references between them (“jalr _printf”)– linker lays them out, and translates referencesLinkers (Linkage editors)!Unix: ld– usually hidden behind compiler!Three functions:– collect together all pieces of a program– coalesce like segments– fix addresses of code and data so the program can run!Result: runnable program stored in new object file!Why can’t compiler do this? – Limited world view: one file, rather than all files!Note *usually*:linkers only shuffle segments, but do not rearrange their internals. – E.g., instructions not reordered; routines that are never called are not removed from a.outSimple linker: two passes needed!Pass 1:– coalesce like segments; arrange in non-overlapping mem.– read file’s symbol table, construct global symbol table with entry for every symbol used or defined– at end: virtual address for each segment known (compute: start+offset)!Pass 2: – patch refs using file and global symbol table– emit result!Symbol table: information about program kept while linker running– segments: name, size, old location, new location– symbols: name, input segment, offset within segmentProb 1: where to put emitted objects? (def)!Compiler:– doesn’t know where data/code should be placed in the process’s address space– assumes everything starts at zero– emits symbol table that holds the name and offset of each created object – routine/variables exported by the file are recorded global definition!Simpler perspective:– code is in a big char array– data is in another big char array– compiler creates (object name, index) tuple for each interesting thing– linker then merges all of these arrays40foo: call printf ret bar: … ret0foo: 0: Tbar: 40: tLinker: where to put emitted objects?!At link time, linker – determines the size of each segment and the resulting address to place each object at– stores all global definitions in a global symbol table that maps the definition to its final virtual address40foo: call printf retbar: ...0foo: 0: Tbar: 40: tprintf:! ...08030ld4040foo: call printfbar: ...4000printf: ...40804110f.oprintf.oa.out (partially done)foo: 4000bar: 4040printf: 4080stabProblem 2: where is everything? (ref)!How to call procedures or reference variables?– E.g., call to printf needs a target addr– compiler places a 0 for the address– emits an external reference telling the
View Full Document
Unlocking...