學(xué)年計算機方向課程大二上ics課件16-linking

1、LinkingIntroduction to Computer Systems16th Lecture, Nov. 14, 2013Instructors: Xiangqun Chen，Junlin LuGuangyu Sun，Xuetao GuanTodayLinkingCase study: Library interpositioningExample C Programint buf2 = 1, 2; int main() swap(); return 0; main.cswap.cextern int buf; int *bufp0 = &buf0;static int *bufp1

2、;void swap() int temp; bufp1 = &buf1; temp = *bufp0; *bufp0 = *bufp1; *bufp1 = temp;Static LinkingPrograms are translated and linked using a compiler 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 filesSep

3、arately compiledrelocatable object filesFully linked executable object file(contains code and data for all functionsdefined in main.c and swap.c)Why Linkers?Reason 1: ModularityProgram can be written as a collection of smaller source files, rather than one monolithic mass.Can build libraries of comm

4、on functions (more on this later)e.g., Math library, standard C libraryWhy Linkers? (cont)Reason 2: EfficiencyTime: Separate compilationChange one source file, compile, and then relink.No need to pile other source files.Space: Libraries Common functions can be aggregated into a single file.Yet execu

5、table files and running memory images contain only code for the functions they actually use.What Do Linkers Do?Step 1. Symbol resolutionPrograms define and reference symbols (global variables and functions):void swap() /* define symbol swap */swap(); /* reference symbol swap */int *xp = &x; /* defin

6、e symbol xp, reference x */Symbol definitions are stored in object file (by compiler) in symbol table.Symbol table is an array of structsEach entry includes name, size, and location of symbol.Linker associates each symbol reference with exactly one symbol definition.What Do Linkers Do? (cont)Step 2.

7、 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.Three Kinds of Object Files (Modules

8、)Relocatable object file (.o 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) fileExecutable object file (a.out file)Contains code and data in a form that can be copied

9、directly into memory and then executed.Shared object file (.so 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 WindowsExecutable and Linkable Format (ELF)Standard binary format

10、 for object filesOne unified format for Relocatable object files (.o), Executable object files (a.out)Shared object files (.so)Generic name: ELF binariesELF Object File FormatElf headerWord size, byte ordering, file type (.o, exec, .so), machine type, etc.Segment header tablePage size, virtual addre

11、sses memory segments (sections), segment sizes.text sectionCode.rodata sectionRead only data: jump tables, .data sectionInitialized global variables.bss sectionUninitialized global variables“Block Started by Symbol”“Better Save Space”Has section header but occupies no spaceELF headerSegment header t

12、able(required for executables).text section.rodata section.bss section.symtab section.rel.txt section.rel.data section.debug sectionSection header table0.data sectionELF Object File Format (cont.).symtab sectionSymbol tableProcedure and static variable namesSection names and locations.rel.text secti

13、onRelocation info for .text sectionAddresses of instructions that will need to be modified in the executableInstructions for modifying.rel.data sectionRelocation info for .data sectionAddresses of pointer data that will need to be modified in the merged executable.debug sectionInfo for symbolic debu

14、gging (gcc -g)Section header tableOffsets and sizes of each sectionELF headerSegment header table(required for executables).text section.rodata section.bss section.symtab section.rel.txt section.rel.data section.debug sectionSection header table0.data sectionLinker SymbolsGlobal symbolsSymbols defin

15、ed by module m that can be referenced by other modules.E.g.: non-static C functions and non-static global variables.External symbolsGlobal symbols that are referenced by module m but defined by some other module.Local symbolsSymbols that are defined and referenced exclusively by module m.E.g.: C fun

16、ctions and global variables defined with the static attribute.Local linker symbols are not local program variablesResolving Symbolsint buf2 = 1, 2; int main() swap(); return 0; main.cextern int buf; int *bufp0 = &buf0;static int *bufp1;void swap() int temp; bufp1 = &buf1; temp = *bufp0; *bufp0 = *bu

17、fp1; *bufp1 = temp;swap.cGlobalExternalExternalLocalGlobalLinker knowsnothing of tempGlobalRelocating Code and Datamain()main.oint *bufp0=&buf0swap()swap.oint buf2=1,2Headersmain()swap()0System codeint *bufp0=&buf0int buf2=1,2System dataMore system codeSystem dataRelocatable Object FilesExecutable O

18、bject File.text.text.data.text.data.text.data.symtab.debug.dataint *bufp1.bssSystem codestatic int *bufp1.bssEven though private to swap, requires allocation in .bssint buf2 = 1,2; int main() swap(); return 0; Relocation Info (main)Disassembly of section .data: 00000000 : 0: 01 00 00 00 02 00 00 00S

19、ource: objdump r d main.omain.cmain.o00000000 : 0: 8d 4c 24 04 lea 0 x4(%esp),%ecx 4: 83 e4 f0 and $0 xfffffff0,%esp 7: ff 71 fc pushl 0 xfffffffc(%ecx) a: 55 push %ebp b: 89 e5 mov %esp,%ebp d: 51 push %ecx e: 83 ec 04 sub $0 x4,%esp 11: e8 fc ff ff ff call 12 12: R_386_PC32 swap 16: b8 00 00 00 00

20、 mov $0 x0,%eax 1b: 83 c4 04 add $0 x4,%esp 1e: 59 pop %ecx 1f: 5d pop %ebp 20: 8d 61 fc lea 0 xfffffffc(%ecx),%esp 23: c3 ret-4Source: objdump -j .data d main.oRelocation Info (swap, .text)extern int buf; int *bufp0 = &buf0;static int *bufp1;void swap() int temp; bufp1 = &buf1; temp = *bufp0; *bufp

21、0 = *bufp1; *bufp1 = temp;swap.cswap.o00000000 : 0: 55 push %ebp 1: 89 e5 mov %esp,%ebp 3: 53 push %ebx 4: c7 05 00 00 00 00 04 movl $0 x4,0 x0 b: 00 00 00 6: R_386_32 .bss a: R_386_32 buf e: 8b 0d 00 00 00 00 mov 0 x0,%ecx 10: R_386_32 bufp014: 8b 19 mov (%ecx),%ebx16: ba 04 00 00 00 mov $0 x4,%edx

22、 17: R_386_32 buf1b: 8b 02 mov (%edx),%eax1d: 89 01 mov %eax,(%ecx)1f: 89 1a mov %ebx,(%edx)21: 5b pop %ebx22: 5d pop %ebp23: c3 retRelocation Info (swap, .data)Disassembly of section .data: 00000000 : 0: 00 00 00 00 0: R_386_32 buf extern int buf; int *bufp0 = &buf0;static int *bufp1;void swap() in

23、t temp; bufp1 = &buf1; temp = *bufp0; *bufp0 = *bufp1; *bufp1 = temp;swap.cExecutable Before/After Relocation (.text)08048374 : 8048374: 8d 4c 24 04 lea 0 x4(%esp),%ecx 8048378: 83 e4 f0 and $0 xfffffff0,%esp 804837b: ff 71 fc pushl 0 xfffffffc(%ecx) 804837e: 55 push %ebp 804837f: 89 e5 mov %esp,%eb

24、p 8048381: 51 push %ecx 8048382: 83 ec 04 sub $0 x4,%esp 8048385: e8 0e 00 00 00 call 8048398 804838a: b8 00 00 00 00 mov $0 x0,%eax 804838f: 83 c4 04 add $0 x4,%esp 8048392: 59 pop %ecx 8048393: 5d pop %ebp 8048394: 8d 61 fc lea 0 xfffffffc(%ecx),%esp 8048397: c3 ret00000000 :. e: 83 ec 04 sub $0 x

25、4,%esp 11: e8 fc ff ff ff call 12 12: R_386_PC32 swap 16: b8 00 00 00 00 mov $0 x0,%eax .Runtime:0 x804838a + 0 xe= 0 x8048398Link time:0 x8048398 + (-4) - 0 x8048386 = 0 xe08048398 : 8048398: 55 push %ebp 8048399: 89 e5 mov %esp,%ebp 804839b: 53 push %ebx 804839c: c7 05 14 96 04 08 04 movl $0 x8049

26、604,0 x8049614 80483a3: 96 04 08 80483a6: 8b 0d 08 96 04 08 mov 0 x8049608,%ecx 80483ac: 8b 19 mov (%ecx),%ebx 80483ae: ba 04 96 04 08 mov $0 x8049604,%edx 80483b3: 8b 02 mov (%edx),%eax 80483b5: 89 01 mov %eax,(%ecx) 80483b7: 89 1a mov %ebx,(%edx) 80483b9: 5b pop %ebx 80483ba: 5d pop %ebp 80483bb:

27、c3 ret00000000 :. 4: c7 05 00 00 00 00 04 movl $0 x4,0 x0 b: 00 00 00 6: R_386_32 .bss a: R_386_32 buf e: 8b 0d 00 00 00 00 mov 0 x0,%ecx 10: R_386_32 bufp014: 8b 19 mov (%ecx),%ebx16: ba 04 00 00 00 mov $0 x4,%edx 17: R_386_32 bufBefore relocationAfter relocationExecutable After Relocation (.data)D

28、isassembly of section .data: 08049600 : 8049600: 01 00 00 00 02 00 00 0008049608 : 8049608: 00 96 04 08Strong and Weak SymbolsProgram symbols are either strong or weakStrong: procedures and initialized globalsWeak: uninitialized globalsint foo=5;p1() int foo;p2() p1.cp2.cstrongweakstrongstrongLinker

29、s Symbol RulesRule 1: Multiple strong symbols are not allowedEach item can be defined only onceOtherwise: Linker errorRule 2: Given a strong symbol and multiple weak symbol, choose the strong symbolReferences to the weak symbol resolve to the strong symbolRule 3: If there are multiple weak symbols,

30、pick an arbitrary oneCan override this with gcc monLinker Puzzlesint x;p1() int x;p2() int x;int y;p1() double x;p2() int x=7;int y=5;p1() double x;p2() int x=7;p1() int x;p2() int x;p1() p1() Link time error: two strong symbols (p1)References to x will refer to the same uninitialized int. Is this w

31、hat you really want?Writes to x in p2 might overwrite y!Evil!Writes to x in p2 will overwrite y!Nasty! Nightmare scenario: two identical weak structs, compiled by different compilerswith different alignment rules. References to x will refer to the same initializedvariable.Role of .h Files#include gl

32、obal.hint f() return g+1;c1.cglobal.h#ifdef INITIALIZEint g = 23;static int init = 1;#elseint g;static int init = 0;#endif#include #include global.hint main() if (!init) g = 37; int t = f(); printf(Calling f yields %dn, t); return 0;c2.cRunning Preprocessor#include global.hint f() return g+1;c1.cglo

33、bal.h#ifdef INITIALIZEint g = 23;static int init = 1;#elseint g;static int init = 0;#endifint g = 23;static int init = 1;int f() return g+1;int g;static int init = 0;int f() return g+1;-DINITIALIZEno initialization#include causes C preprocessor to insert file verbatim (Use gcc E to view result)Globa

34、l VariablesAvoid if you canOtherwiseUse static if you canInitialize if you define a global variableUse extern if you use external global variablePackaging Commonly Used FunctionsHow to package functions commonly used by programmers?Math, I/O, memory management, string manipulation, etc.Awkward, give

35、n the linker framework so far:Option 1: Put all functions into a single source fileProgrammers link big object file into their programsSpace and time inefficientOption 2: Put each function in a separate source fileProgrammers explicitly link appropriate binaries into their programsMore efficient, bu

36、t burdensome on the programmerSolution: Static LibrariesStatic libraries (.a archive files)Concatenate related relocatable object files into a single file with an index (called an archive).Enhance linker so that it tries to resolve unresolved external references by looking for the symbols in one or

37、more archives.If an archive member file resolves reference, link it into the executable.Creating Static LibrariesTranslatoratoi.catoi.oTranslatorprintf.cprintf.olibc.aArchiver (ar).Translatorrandom.crandom.ounix ar rs libc.a atoi.o printf.o random.oC standard libraryArchiver allows incremental updat

38、es pile function that changes and replace .o file in archive.Commonly Used Librarieslibc.a (the C standard library)8 MB archive of 1392 object files.I/O, memory allocation, signal handling, string handling, data and time, random numbers, integer mathlibm.a (the C math library)1 MB archive of 401 obj

39、ect files. floating point math (sin, cos, tan, log, exp, sqrt, ) % ar -t /usr/lib/libc.a | sort fork.o fprintf.o fpu_control.o fputc.o freopen.o fscanf.o fseek.o fstab.o % ar -t /usr/lib/libm.a | sort e_acos.o e_acosf.o e_acosh.o e_acoshf.o e_acoshl.o e_acosl.o e_asin.o e_asinf.o e_asinl.o Linking w

40、ith Static LibrariesTranslators(cpp, cc1, as)main2.cmain2.olibc.aLinker (ld)p2printf.o and any other modules called by printf.o libvector.aaddvec.oStatic librariesRelocatableobject filesFully linked executable object filevector.hArchiver(ar)addvec.omultvec.oUsing Static LibrariesLinkers algorithm fo

41、r resolving external references:Scan .o files and .a files in the command line order.During the scan, keep a list of the current unresolved references.As each new .o or .a file, obj, is encountered, try to resolve each unresolved reference in the list against the symbols defined in obj. If any entri

42、es in the unresolved list at end of scan, then error.Problem:Command line order matters!Moral: put libraries at the end of the command line. unix gcc -L. libtest.o -lmine unix gcc -L. -lmine libtest.o libtest.o: In function main: libtest.o(.text+0 x4): undefined reference to libfun Loading Executabl

43、e Object FilesELF headerProgram header table(required for executables).text section.data section.bss section.symtab.debugSection header table(required for relocatables)0Executable Object FileKernel virtual memoryMemory-mapped region forshared librariesRun-time heap(created by malloc)User stack(creat

44、ed at runtime)Unused0%esp (stack pointer)Memoryoutside 32-bitaddress spacebrk0 x1000000000 x080480000 xf7e9ddc0Read/write segment(.data, .bss)Read-only segment(.init, .text, .rodata)Loaded from the executable file.rodata section.line.init section.strtabShared LibrariesStatic libraries have the follo

45、wing disadvantages:Duplication in the stored executables (every function need std libc)Duplication in the running executablesMinor bug fixes of system libraries require each application to explicitly relinkModern solution: Shared Libraries Object files that contain code and data that are loaded and

46、linked into an application dynamically, at either load-time or run-timeAlso called: dynamic link libraries, DLLs, .so filesShared Libraries (cont.)Dynamic linking can occur when executable is first loaded and run (load-time linking).Common case for Linux, handled automatically by the dynamic linker

47、(ld-linux.so).Standard C library (libc.so) usually dynamically linked. Dynamic linking can also occur after program has begun (run-time linking).In Linux, this is done by calls to the dlopen() interface.Distributing software.High-performance web servers. Runtime library interpositioning.Shared libra

48、ry routines can be shared by multiple processes.More on this when we learn about virtual memoryDynamic Linking at Load-timeTranslators (cpp, cc1, as)main2.cmain2.olibc.solibvector.soLinker (ld)p2Dynamic linker (ld-linux.so)Relocation and symbol table infolibc.solibvector.soCode and dataPartially lin

49、ked executable object fileRelocatableobject fileFully linked executablein memoryvector.hLoader (execve)unix gcc -shared -o libvector.so addvec.c multvec.cDynamic Linking at Run-time#include #include int x2 = 1, 2;int y2 = 3, 4;int z2;int main() void *handle; void (*addvec)(int *, int *, int *, int);

50、 char *error; /* Dynamically load the shared lib that contains addvec() */ handle = dlopen(./libvector.so, RTLD_LAZY); if (!handle) fprintf(stderr, %sn, dlerror();exit(1); Dynamic Linking at Run-time . /* Get a pointer to the addvec() function we just loaded */ addvec = dlsym(handle, addvec); if (er

51、ror = dlerror() != NULL) fprintf(stderr, %sn, error);exit(1); /* Now we can call addvec() just like any other function */ addvec(x, y, z, 2); printf(z = %d %dn, z0, z1); /* unload the shared library */ if (dlclose(handle) 0) fprintf(stderr, %sn, dlerror();exit(1); return 0;Linking SummaryLinking is

52、a technique that allows programs to be constructed from multiple object files. Linking can happen at different times in a programs lifetime:Compile time (when a program is compiled)Load time (when a program is loaded into memory)Run time (while a program is executing)Understanding linking can help y

53、ou avoid nasty errors and make you a better programmer. TodayLinkingCase study: Library interpositioningCase Study: Library InterpositioningLibrary interpositioning : powerful linking technique that allows programmers to intercept calls to arbitrary functionsInterpositioning can occur at:Compile tim

54、e: When the source code is compiledLink time: When the relocatable object files are statically linked to form an executable object fileLoad/run time: When an executable object file is loaded into memory, dynamically linked, and then executed.Some Interpositioning ApplicationsSecurityConfinement (san

55、dboxing)Interpose calls to libc functions.Behind the scenes encryptionAutomatically encrypt otherwise unencrypted network connections.Monitoring and ProfilingCount number of calls to functionsCharacterize call sites and arguments to functionsMalloc tracingDetecting memory leaksGenerating address tra

56、cesExample programGoal: trace the addresses and sizes of the allocated and freed blocks, without modifying the source code. Three solutions: interpose on the lib malloc and free functions at compile time, link time, and load/run time. #include #include #include int main() free(malloc(10); printf(hel

57、lo, worldn); exit(0);hello.cCompile-time Interpositioning#ifdef COMPILETIME/* Compile-time interposition of malloc and free using C * preprocessor. A local malloc.h file defines malloc (free) * as wrappers mymalloc (myfree) respectively. */#include #include /* * mymalloc - malloc wrapper function */

58、void *mymalloc(size_t size, char *file, int line) void *ptr = malloc(size); printf(%s:%d: malloc(%d)=%pn, file, line, (int)size, ptr); return ptr;mymalloc.cCompile-time Interpositioning#define malloc(size) mymalloc(size, _FILE_, _LINE_ )#define free(ptr) myfree(ptr, _FILE_, _LINE_ )void *mymalloc(si

59、ze_t size, char *file, int line);void myfree(void *ptr, char *file, int line);malloc.hlinux make hellocgcc -O2 -Wall PILETIME -c mymalloc.cgcc -O2 -Wall -I. -o helloc hello.c mymalloc.olinux make runc./hellochello.c:7: malloc(10)=0 x501010hello.c:7: free(0 x501010)hello, worldLink-time Interpositioning#ifdef LINKTIME/* Link-time interposition of malloc and free using the static linkers (ld) -wrap symbol flag. */#include void *_real_malloc(size