Generating Programs and LinkingCSCI 3753 AnnouncementsOperating System ArchitectureWhat is an Application?Loading and Executing a ProgramSlide 6Generating a Program’s Binary ExecutableLinking Multiple Object Files Into an ExecutableSlide 9Linker Resolves Unknown SymbolsSlide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Linker Relocates AddressesLinked ELF Executable Object FileLoading Executable Object FilesGenerating Programs and LinkingProfessor Rick HanDepartment of Computer ScienceUniversity of Colorado at BoulderCSCI 3753 Announcements•Moodle - posted last Thursday’s lecture•Programming shell assignment 0 due Thursday at 11:55 pm, not 11 am•Introduction to Operating Systems•Read Chapters 3 and 4 in the textbookSystem Libraries and Tools(Compilers, Shells, GUIs)Operating System ArchitectureApp3DiskMemoryCPU Display MouseApp2App1I/O Scheduler VMFileSystem OS“Kernel”Posix, Win32,Java, C library APISystem call APIDeviceManagerWhat is an Application?•A software program consist of a sequence of code instructions and data–for now, let a simple app = a program•Computer executes the instructions line by line–code instructions operate on dataCodeDataProgram P1CPUProgramCounter (PC)RegistersALUFetch Codeand DataWrite DataCodeDataMainMemoryOS LoaderProgramP1binaryLoading and Executing a ProgramCodeDataCodeDataP1binaryP2binaryDiskLoading and Executing a ProgramCodeDataCodeDataCodeDataP1binaryP2binaryDiskMainMemoryOS LoaderProgramP1binaryshift left by 2 register R1and put in address Ainvoke low level systemcall n to OS: syscall njump to address BMachine Code instructionsof binary executableGenerating a Program’s Binary Executable•We program source code in a high-level language like C or Java, and use tools like compilers to create a program’s binary executableCodeProgram P1’sBinaryExecutableSourceCodeCompilerfile P1.cAssembler LinkerDatagcc can generate any of these stagesP1.sP1.otechnically, there is a preprocessing step before the compiler.“gcc -c” will generate relocatable object files, and not run linkerLinking Multiple Object Files Into an Executable•linker combines multiple .o object files into one binary executable file–why split a program into multiple objects and then relink them?–breaking up a program into multiple files, and compiling them separately, reduces amount of recompilation if a single file is edited•don’t have to recompile entire program, just the object file of the changed source file, then relink object filesCodeP1 or P1.exeSourceCodeCompilercc1file P1.cAssemblerasLinkerldDataP1.sP1.ofoo2.ofoo3.oLinking Multiple Object Files Into an Executable•in combining multiple object files, the linker must –resolve references to variables and functions defined in other object files - this is called symbol resolution–relocate each object’s internal addresses so that the executable’s combination of objects is consistent in its memory references•an object’s code and data are compiled in its own private world to start at address zeroCodeP1 or P1.exeSourceCodeCompilercc1file P1.cAssemblerasLinkerldDataP1.sP1.ofoo2.ofoo3.oLinker Resolves Unknown SymbolsP1.cint globalvar1=0;main(...) { ----- f1(...) -----}foo2.cvoid f1(...) { ----}void f2(...) { ---- globalvar1 = 4; ----} extern void f1(...); extern int globalvar1;P1.othe P1.o object file will contain a list ofunknown symbols, e.g. f1, in a symbol tablefoo2.ofoo2.o’s symbol table listsunknown symbols, e.g. globalvar1Linker Resolves Unknown Symbols•ELF relocatable object file contains following sections:–ELF header (type, size, size/# sections)–code (.text)–data (.data, .bss, .rodata)•.data = initialized global variables•.bss = uninitialized global variables (does not actually occupy space on disk, just a placeholder)–symbol table (.symtab)–relocation info (.rel.text, .rel.data)–debug symbol table (.debug only if “-g” compile flag used)–line info (map C & .text line #s only if “-g”)–string table (for symbol tables)ELF header.text.rodata.data.bss.symtab.rel.text.rel.data.debug.line.strtabSection header tableELF relocatable object fileLinker Resolves Unknown Symbols•Symbol table contains 3 types of symbols:–global symbols - defined in this object–global symbols referenced but not defined here–local symbols defined and referenced exclusively by this object, e.g. static global variables and functions•local symbols are not equivalent to local variables, which get allocated on the stack at run timeLinker Resolves Unknown Symbolsextern float f1();int globalvar1=0;void f2(...) { static int x=-1; ----- }global symbols defined hereglobal symbol referenced herebut defined elsewhere“local” symbol•The symbol table informs the Linker where symbols referenced or referenceable by each object file can be found:–if another file references globalvar1, then look here for info–if this file reference f2, then another object file’s symbol table will mention f2Linker Resolves Unknown Symbols•Each entry in the ELF symbol table looks like:typedef struct { int name; /* string table offset */ int value; /* section offset or VM address */ int size; /* object size in bytes */ char type:4, /* data, func, section or src file name (4 bits) */ binding:4;/* local or global (4 bits) */ char reserved; /* unused */ char section; /* section header index, ABS, UNDEF, */} ELF_Symbol;here’s where we flag the undefined statusLinker Resolves Unknown Symbols•During linking, the linker goes through each input object file and determines if unknown symbols are defined in other object filesLinkerCodeData.symtabP1.o relocatableobject fileCodeData.symtabP2.oCodeData.symtabP3.ofunction f1() in P1.ois referenced butnot defined, henceunknowndefinedin P2?Nodefined inP3?YesLinker Resolves Unknown Symbols•What if two object files use the same name for a global variable?–Linker resolves multiply defined global symbols–functions and initialized global variables are defined as strong symbols, while uninitialized global variables are weak symbolsRule 1: multiple strong symbols are not allowedRule 2: choose the strong symbol over the weak symbolRule 3: given multiple weak symbols, choose any oneLinker Resolves Unknown Symbols•Linking with static libraries–Bundle together many related .o files together into a single file called a library or .a