Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38LinkingFebruary 28, 2008TopicsTopicsStatic linkingDynamic linkingCase study: Library interpositioningclass13.ppt15-213“The course that gives CMU its Zip!”215-213, S’08Meta-AnnouncementsLook for announcements onLook for announcements onGentler grading formula for Performance LabUpgrade in correctness checking for sameExamsExamsTarget: Monday recitationI have somebody's hatI have somebody's hat315-213, S’08Example C Programint buf[2] = {1, 2}; int main() { swap(); return 0;} main.c swap.cextern int buf[]; static int *bufp0 = &buf[0];static int *bufp1;void swap(){ int temp; bufp1 = &buf[1]; temp = *bufp0; *bufp0 = *bufp1; *bufp1 = temp;}415-213, S’08Static LinkingPrograms are translated and linked using a Programs are translated and linked using a compiler drivercompiler driver::unix> gcc -O2 -g -o p main.c swap.cunix> ./pLinker (ld)Translators(cpp, cc1, as)main.cmain.oTranslators(cpp, cc1, as)swap.cswap.opSource filesSeparately compiledrelocatable object filesFully linked executable object file(contains code and data for all functionsdefined in main.c and swap.c515-213, S’08Why Linkers?Reason 1: ModularityReason 1: ModularityProgram can be written as a collection of smaller source files, rather than one monolithic mass.Can build libraries of common functions (more on this later)e.g., Math library, standard C library615-213, S’08Why Linkers? (cont)Reason 2: EfficiencyReason 2: EfficiencyTime: Separate CompilationChange one source file, compile, and then relink.No need to recompile other source files.Space: Libraries Common functions can be aggregated into a single file...Yet executable files and running memory images contain only code for the functions they actually use.715-213, S’08What Do Linkers Do?Step 1. Symbol resolutionStep 1. Symbol resolutionPrograms define and reference symbols (variables and functions):void swap() {…} /* define symbol swap */swap(); /* reference symbol swap */int *xp = &x; /* define xp, reference x */Symbol definitions are stored (by compiler) in symbol table.Symbol table is an array of structsEach entry includes name, type, size, and location of symbol.Linker associates each symbol reference with exactly one symbol definition.815-213, S’08What Do Linkers Do? (cont)Step 2. RelocationStep 2. RelocationMerges separate code and data sections into single sectionsRelocates symbols from their relative locations in the .o files to their final absolute memory locations in the executable.Updates all references to these symbols to reflect their new positions.915-213, S’08Three Kinds of Object Files (Modules)1. Relocatable object file (1. Relocatable object file (.o.o file) file)Contains code and data in a form that can be combined with other relocatable object files to form executable object file.Each .o file is produced from exactly one source (.c) file2. Executable object file 2. Executable object file Contains code and data in a form that can be copied directly into memory and then executed.3. Shared object file (3. Shared object file (.so.so file) file)Special type of relocatable object file that can be loaded into memory and linked dynamically, at either load time or run-time.Called Dynamic Link Libraries (DLLs) by Windows1015-213, S’08Executable and Linkable Format (ELF)Standard binary format for object filesStandard binary format for object filesOriginally proposed by AT&T System V UnixOriginally proposed by AT&T System V UnixLater adopted by BSD Unix variants and LinuxOne unified format for One unified format for Relocatable object files (.o), Executable object filesShared object files (.so)Generic name: ELF binariesGeneric name: ELF binaries1115-213, S’08ELF Object File FormatElf headerElf headerMagic number, type (.o, exec, .so), machine, byte ordering, etc.Segment header tableSegment header tablePage size, virtual addresses memory segments (sections), segment sizes..text.text section sectionCode.data.data section sectionInitialized global variables.bss.bss section sectionUninitialized global variables“Block Started by Symbol”“Better Save Space”Has section header but occupies no spaceELF headerSegment header table(required for executables).text section.data section.bss section.symtab section.rel.txt section.rel.data section.debug sectionSection header table01215-213, S’08ELF Object File Format (cont).symtab.symtab section sectionSymbol tableProcedure and static variable namesSection names and locations.rel.text.rel.text section sectionRelocation info for .text sectionAddresses of instructions that will need to be modified in the executableInstructions for modifying..rel.data.rel.data section sectionRelocation info for .data sectionAddresses of pointer data that will need to be modified in the merged executable.debug.debug section sectionInfo for symbolic debugging (gcc -g)Section header tableSection header tableOffsets and sizes of each sectionELF headerSegment header table(required for executables).text section.data section.bss section.symtab section.rel.text section.rel.data section.debug sectionSection header table01315-213, S’08Linker SymbolsGlobal symbolsGlobal symbolsSymbols defined by module m that can be referenced by other modules.Ex: non-static C functions and non-static global variables.External symbolsExternal symbolsGlobal symbols that are referenced by module m but defined by some other module.Local symbolsLocal symbolsSymbols that are defined and referenced exclusively by module m.Ex: C functions and variables defined with the static attribute.Key Point: Local linker symbols are Key Point: Local linker symbols are notnot local program local program variablesvariables1415-213, S’08Resolving Symbolsint buf[2] = {1,2}; int main() { swap(); return 0;} main.cswap.cextern int buf[]; static int *bufp0 = &buf[0];static int *bufp1;void swap(){ int temp; bufp1 = &buf[1]; temp = *bufp0; *bufp0 = *bufp1; *bufp1 = temp;}Def of global symbol bufRef to external symbol bufRef to external symbol swapDef of
View Full Document