============= Linkage order ============= In short: When you invoke the linker the order of object files does not matter, but the order of static libraries does matter. For exemplification we construct some simple toy examples where two libraries `libfoo.a` and `libbar.a` are used by a test program `xtest`. For showing you how this is relevant in the real world these examples are first realized in C and the GNU compiler and linker are used. You will also see that in the real world there many technical and platform dependant details are hidden. We will not completely reveal all of them but at least point to them. The intension is that you see enough from the real world so that you understand that the essential things are reflected by the ULM tools. The quiz at the end of this page makes some references to this __question on stackoverflow__. This is supposed to show you that we are dealing with things that actually have some practical relevance. And most of all, understanding what these guys are talking about should give you some confidence ;-) GNU Linker: Example from the real world ======================================= From Session 10 you already got the idea that C code is just a more abstract, platform independent description of assembly code. So when we use examples in C we just hide details about the instruction set of the underlying architecture or about the used calling conventions. The C compiler takes care of this details and produces the proper assembly code. So looking at the following C code you know how to implement it equivalently in assembly for the ULM. Now just belief that for any other architecture the assembly code is essentially the same: + :import: session11/libdep_gcc/xtest.c + :import: session11/libdep_gcc/foo.c + :import: session11/libdep_gcc/bar.c With `gcc` you can generate an executable from this source files with a single command: ---- SHELL (path=session11/libdep_gcc) ----------------------------------------- gcc -o xtest xtest.c foo.c bar.c -------------------------------------------------------------------------------- This command appears harmless but hides quite a few things. Using the option `-v` you can see that __`gcc`__ is used here as a convenient wrapper for calling a C compiler, assembler and linker. Don't be shy unfold the following shell box and breathe in some of the details: ---- SHELL (path=session11/libdep_gcc, fold) ----------------------------------- gcc -v -o xtest xtest.c foo.c bar.c -------------------------------------------------------------------------------- Simplified (we neglect the C preprocessor) you can describe what is going on behind the scene by this flowchart: ---- TIKZ ---------------------------------------------------------------------- \begin{tikzpicture} \input{flowchart.tex} \renewcommand\BoxWidth {3} \renewcommand\FlowColDist {7} \renewcommand\BoxHeight {1.2} \renewcommand\BoxDistance {2.2} %\SetMargin{1}{2}{1}{1} \renewcommand\FlowCol {0} \PutStatement{0}{xtest.c} \PutStatement{1}{xtest.s} \PutStatement{2}{xtest.o} \renewcommand\FlowCol {1} \PutStatement{0}{foo.c} \PutStatement{1}{foo.s} \PutStatement{2}{foo.o} \renewcommand\FlowCol {2} \PutStatement{0}{bar.c} \PutStatement{1}{bar.s} \PutStatement{2}{bar.o} \renewcommand\FlowCol {3} \PutStatement{2}{some libraries} \renewcommand\FlowCol {1} \PutStatement{4}{xtest} \AddGenPath{0}{1}{0}{0}{GNU C compiler generates} \AddGenPath{0}{2}{0}{1}{GNU assembler generates} \AddGenPath{1}{1}{1}{0}{GNU C compiler generates} \AddGenPath{1}{2}{1}{1}{GNU assembler generates} \AddGenPath{2}{1}{2}{0}{GNU C compiler generates} \AddGenPath{2}{2}{2}{1}{GNU assembler generates} \AddGenPath[above=1cm]{1}{4}{0}{2}{GNU linker generates} \AddGenPath{1}{4}{2}{2}{} \AddGenPath{1}{4}{1}{2}{} \AddGenPath{1}{4}{3}{2}{} \end{tikzpicture} -------------------------------------------------------------------------------- What is denoted as "some libraries" hides code for communicating with the operating system. For instance, it contains a `_start` function which calls function `main` and returns its return value as exit code, and function `puts` for printing some text. Some truths just for completeness ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Truth be told, these libraries are so called __shared libraries__, and on Windows they are called __Dynamic-link libraries (DLLs)__. Compared to static libraries the details behind shared libraries are a bit harder to explain and they don't solve any problem that is relevant for us. Hence we just scratch this topic by mentioning it. On Linux (try the following on `heim`) the topic _shared libraries_ can be postponed until there is an actual need for them. If you use the option `-static` all libraries involved are actually are static libraries: ---- SHELL (path=session11/libdep_gcc, hostname=heim, fold) -------------------- gcc -static -v -o xtest xtest.c foo.c bar.c -------------------------------------------------------------------------------- On other systems like Windows, MacOS or Solaris (which runs on `theon`) you would get a linker error because the vendors don't ship all required static libraries. In this article __Static Linking - where did it go__ you can find some explanation about the background. Generate the object files ------------------------- Using the option `-c` the tool chain behind `gcc` stops after the C code was translated into an object file: ---- SHELL (path=session11/libdep_gcc) ----------------------------------------- gcc -c xtest.c gcc -c foo.c gcc -c bar.c -------------------------------------------------------------------------------- In the following we use these to exemplify how the GNU linker processes objects and static libraries. Linking object files -------------------- Like the ULM linker all object files that the GNU linker receives are combined. Regardless whether they are required to resolve undefined symbols. The advantage of that is that the order of the objects does not matter: ---- SHELL (path=session11/libdep_gcc) ----------------------------------------- gcc -o xtest xtest.o foo.o bar.o xtest gcc -o xtest xtest.o bar.o foo.o xtest gcc -o xtest bar.o foo.o xtest.o xtest -------------------------------------------------------------------------------- The disadvantage is that the executables might contain object files that are unused. Generating and linking static libraries --------------------------------------- Next we generate two static libraries that store `foo.o` and `bar.o` respectively: ---- SHELL (path=session11/libdep_gcc, hide) ----------------------------------- rm -f libfoo.a libbar.a -------------------------------------------------------------------------------- ---- SHELL (path=session11/libdep_gcc) ----------------------------------------- ar cru libfoo.a foo.o ranlib libfoo.a ar cru libbar.a bar.o ranlib libbar.a -------------------------------------------------------------------------------- Besides the object file each archive contains an index as member. However, the `ar` command on Solaris does not print that if you use the `-t` option: ---- SHELL (path=session11/libdep_gcc) ----------------------------------------- ar t libfoo.a ar t libbar.a -------------------------------------------------------------------------------- Note that there are actually different `ranlib` implementations in the real world. On Linux and Solaris usually __GNU ranlib__ is installed (which hides the index), on MacOS it is by default __BSD ranlib__ (which does not hide the index). Read about __ranlib on wikipedia__ to get a overview of popular implementations and how they differ. On Solaris and Linux you can see the index with with `nm -s`: ---- SHELL (path=session11/libdep_gcc) ----------------------------------------- nm -s libfoo.a nm -s libbar.a -------------------------------------------------------------------------------- Now this will be the only order that works: ---- SHELL (path=session11/libdep_gcc) ----------------------------------------- gcc -o xtest xtest.o libfoo.a libbar.a xtest -------------------------------------------------------------------------------- Any other order will result in a linker error. For example ---- SHELL (path=session11/libdep_gcc) ----------------------------------------- gcc -o xtest xtest.o libbar.a libfoo.a -------------------------------------------------------------------------------- or ---- SHELL (path=session11/libdep_gcc) ----------------------------------------- gcc -o xtest libfoo.a libbar.a xtest.o -------------------------------------------------------------------------------- ULM Linker: Example for non-circular dependencies ================================================= The real world is ugly and harsh and in teaching you either have to hide some details (the "some library" or "shared library" stuff) or you just can mention them (but there is no time to reveal all the details). Therefore we resemble the real world example with the ULM tools. The advantage is that we exactly know what is going on here. There will be no "some libraries" involved for "doing something you can not (and don't have to) understand in detail". The adapted example consists of three source files and the following call tree: ---- TIKZ ---------------------------------------------------------------------- \begin{tikzpicture} \input{flowchart.tex} \renewcommand\BoxWidth{5} \renewcommand\FlowColDist{(\BoxWidth+2.5)} \SetMargin{0}{10}{0}{3} \Compilation{3}{source file: xtest.s} \PutStatement{0}{init stack} \PutLabel{0}{\_start} \PutCallStatement[red!50]{1}{call function foo } \PutStatement{2}{halt with return value} \AddPath{0}{1} \AddPath{1}{2} \PutAnnotation{0}{\text{Entry point}} % next flow chart column \renewcommand\FlowCol{1} \Compilation{3}{source file: foo.s} \PutStatement{0}{do something} \PutLabel{0}{foo} \PutCallStatement[orange!50]{1}{ call function bar } \PutStatement{2}{do something} \PutStatement{3}{return exit code} \AddPath{0}{1} \AddPath{1}{2} \AddPath{2}{3} \DrawCallPointer[red!50]{0}{1}{1}{0} \DrawReturnPointer[red!50]{0}{1}{1}{3} % next flow chart column \renewcommand\FlowCol{2} \Compilation{3}{source file: bar.s} \PutStatement{0}{do something} \PutLabel{0}{bar} \PutStatement{1}{return} \AddPath{0}{1} \renewcommand{\CallPointerPadToY}{0} \DrawCallPointer[orange!50]{1}{1}{2}{0} \DrawReturnPointer[orange!50]{1}{1}{2}{1} \end{tikzpicture} -------------------------------------------------------------------------------- In the implementation the calling convention from Session 11 is used as we have non-leaf functions here. In reality we would have at least 5 function (`_start`, `puts`, `main`, `foo` and `bar`) here we simplify things: - Think of `xtest.s` as a merged combination of the `_start` and `main` function: :import: session11/libdep/xtest.s [fold] - Instead of calling an extra function `puts` the strings are printed character by character using hard coded `putc` instructions: :import: session11/libdep/foo.s [fold] :import: session11/libdep/bar.s [fold] As in the examples with `gcc` we generate object files and static libraries. Using the ULM tools we can understand in more detail how linkage is done. Order of object files does not matter ------------------------------------- First create the object files: ---- SHELL (path=session11/libdep) --------------------------------------------- ulmas -o xtest.o xtest.s ulmas -o foo.o foo.s ulmas -o bar.o bar.s -------------------------------------------------------------------------------- Now pass the object files to the linker in an arbitrary order. Here you see 3 of the 6 possibilities: ---- SHELL (path=session11/libdep) --------------------------------------------- ulmld -o xtest xtest.o foo.o bar.o ulm xtest ulmld -o xtest xtest.o bar.o foo.o ulm xtest ulmld -o xtest bar.o foo.o xtest.o ulm xtest -------------------------------------------------------------------------------- The order does not matter because an object files is always imported. This has the drawback that the executable might contain unused code. But the advantage is that we don't have to think about the order. As long as in the union of all objects all symbols can be resolved we get an executable. Order of static libraries does matter ------------------------------------- Now we create the static libraries: ---- SHELL (path=session11/libdep) --------------------------------------------- ar cru libfoo.a foo.o ulmranlib libfoo.a ar cru libbar.a bar.o ulmranlib libbar.a -------------------------------------------------------------------------------- The linker processes arguments in the order they appear. Recall, if a static library is passed only object files are picked from it if they resolve at least one undefined symbol. - The only order that allows the linker to resolve all symbols is as follows: ---- SHELL (path=session11/libdep) ------------------------------------------- ulmld -o xtest xtest.o libfoo.a libbar.a ------------------------------------------------------------------------------ The linker first reads in the complete object file `xtest.o`. This defines (and exports) the symbol `_start` which is required for an executable but has one unresolved symbol `foo`: ---- SHELL (path=session11/libdep) ------------------------------------------- grep "^T" xtest.o | grep _start grep "^U" xtest.o ------------------------------------------------------------------------------ Then the linker processes the static library `libfoo.a`. That means it checks if it contains an object file that can resolve the undefined symbol `foo`. For that the index of the library is searched. We can do this manually with ---- SHELL (path=session11/libdep) ------------------------------------------- ar x libfoo.a __SYMTAB_INDEX grep foo __SYMTAB_INDEX ------------------------------------------------------------------------------ Because of that the linker will import the object file `foo.o` from the library. This leads to another unresolved symbol `bar`: ---- SHELL (path=session11/libdep) ------------------------------------------- ar x libfoo.a foo.o grep "^U" foo.o ------------------------------------------------------------------------------ This symbol can not be resolved by an object file stored in `libfoo.a`: ---- SHELL (path=session11/libdep) ------------------------------------------- ar x libfoo.a __SYMTAB_INDEX grep bar __SYMTAB_INDEX ------------------------------------------------------------------------------ Hence the next argument gets processed which is `libbar.a`. Again the linker checks if it contains objects that resolve a undefined symbol, in this case `bar`: ---- SHELL (path=session11/libdep) ------------------------------------------- ar x libbar.a __SYMTAB_INDEX grep bar __SYMTAB_INDEX ------------------------------------------------------------------------------ After picking `bar.o` from the library no more undefined symbols exist: ---- SHELL (path=session11/libdep) ------------------------------------------- ar x libbar.a bar.o grep "^U" bar.o ------------------------------------------------------------------------------ Hence linkage is successful and an executable gets created. - Let's reproduce why other orders fail. For example this order: ---- SHELL (path=session11/libdep) ------------------------------------------- ulmld -o xtest xtest.o libbar.a libfoo.a ------------------------------------------------------------------------------- After processing `xtest.o` the list of undefined symbols again just consists of `foo`. As this is not contained in `libbar.a` nothing gets extracted. The argument is `libfoo.a` which resolves `foo` but introduces the undefined symbol `bar`. - Also consider this order: ---- SHELL (path=session11/libdep) ------------------------------------------- ulmld -o xtest libfoo.a libbar.a xtest.o ------------------------------------------------------------------------------ In this example neither `libfoo.a` nor `libbar.a` contains an object file that defines `_start`. Hence nothing gets imported from them. Hence the linker only reads in `xtest.o` which results in the unresolved symbol `foo`. Quiz13: Circular dependencies ============================= In general static libraries can have circular dependencies, e.g. `libfoo.a` depends on `libbar.a`, and `libbar.a` depends on `libfoo.a`. We will not discuss whether this form of dependencies indicate that something is wrong about the overall design of the libraries (most likely it can be avoided by rethinking things). Just read this __question on stackoverflow__ to see that you have to face this things in the real world whether you like it or not. For the quiz you have to submit 4 files `submit hpc quiz14 notes.txt xtest.o libfoo.a libbar.a` Here a brief description of these files: - `xtest.o` is an object file for a test program, - `libfoo.a` and `libbar.a` are static libraries and - in `notes.txt` you can use to give some free style answers to different questions. The details about these files are as follows: - You have to write 7 functions in separate translation units as outlined in this flow chart: ---- TIKZ -------------------------------------------------------------------- \begin{tikzpicture} \input{flowchart.tex} \renewcommand\BoxWidth{5} \renewcommand\FlowColDist{(\BoxWidth+2.5)} \SetMargin{0}{10}{0}{3} \Compilation{3}{source file: xtest.s} \PutStatement{0}{init stack} \PutLabel{0}{\_start} \PutCallStatement[red!50]{1}{call function foo1 } \PutStatement{2}{halt with exit code 0} \AddPath{0}{1} \AddPath{1}{2} \PutAnnotation{0}{\text{Entry point}} % next flow chart column \renewcommand\FlowCol{1} \Compilation{3}{source file: foo1.s} \PutStatement{0}{do something} \PutLabel{0}{foo1} \PutCallStatement[orange!50]{1}{ call function bar1 } \PutStatement{2}{do something} \PutStatement{3}{return} \AddPath{0}{1} \AddPath{1}{2} \AddPath{2}{3} \Compilation[6]{9}{source file: foo2.s} \PutStatement{6}{do something} \PutLabel{6}{foo2} \PutCallStatement[orange!50]{7}{ call function bar2 } \PutStatement{8}{do something} \PutStatement{9}{return} \AddPath{6}{7} \AddPath{7}{8} \AddPath{8}{9} \Compilation[12]{15}{source file: foo3.s} \PutStatement{12}{do something} \PutLabel{12}{foo3} \PutCallStatement[orange!50]{13}{ call function bar3 } \PutStatement{14}{do something} \PutStatement{15}{return} \AddPath{12}{13} \AddPath{13}{14} \AddPath{14}{15} \DrawCallPointer[red!50]{0}{1}{1}{0} \DrawReturnPointer[red!50]{0}{1}{1}{3} % next flow chart column \renewcommand\FlowCol{2} \Compilation{3}{source file: bar1.s} \PutStatement{0}{do something} \PutLabel{0}{bar1} \PutCallStatement[orange!50]{1}{ call function foo1 } \PutStatement{2}{do something} \PutStatement{3}{return} \AddPath{0}{1} \AddPath{1}{2} \AddPath{2}{3} \Compilation[6]{9}{source file: bar2.s} \PutStatement{6}{do something} \PutLabel{6}{bar2} \PutCallStatement[orange!50]{7}{ call function foo3 } \PutStatement{8}{do something} \PutStatement{9}{return} \AddPath{6}{7} \AddPath{7}{8} \AddPath{8}{9} \Compilation[12]{14}{source file: bar3.s} \PutStatement{12}{do something} \PutLabel{12}{bar3} \PutStatement{13}{return} \AddPath{12}{13} \renewcommand{\CallPointerPadToY}{0} \DrawCallPointer[orange!50]{1}{1}{2}{0} \DrawReturnPointer[orange!50]{1}{1}{2}{3} \DrawCallPointerLeft[red!50]{2}{1}{1}{6} \DrawReturnPointerLeft[red!50]{2}{1}{1}{9} \DrawCallPointer[orange!50]{1}{7}{2}{6} \DrawReturnPointer[orange!50]{1}{7}{2}{9} \DrawCallPointerLeft[red!50]{2}{7}{1}{12} \DrawReturnPointerLeft[red!50]{2}{7}{1}{15} \DrawCallPointer[orange!50]{1}{13}{2}{12} \DrawReturnPointer[orange!50]{1}{13}{2}{13} \end{tikzpicture} ------------------------------------------------------------------------------ - In the implementation the "do something" should print some text so that you can trace the call tree by running the program without using a debugger (we want something simple). - Use the ULM assembler to generate object files for each translation unit. You don't have to write a makefile for that (but you can), i.e. you can do that manually: ---- CODE (type=txt) --------------------------------------------------------- ulmas -o xtest.o xtest.s ulmas -o foo1.o foo1.s ulmas -o foo2.o foo2.s ulmas -o foo3.o foo3.s ulmas -o bar1.o bar1.s ulmas -o bar2.o bar2.s ulmas -o bar3.o bar3.s ------------------------------------------------------------------------------ Or by using the `bash` as follows (I hope such examples motivate you to learn more about `bash`): ---- CODE (type=txt) --------------------------------------------------------- for i in *.s; do ulmas -o ${i#.s}.o $i; done ------------------------------------------------------------------------------ - Create the static libraries `libfoo.a` and `libbar.a` as follows: ---- CODE (type=txt) --------------------------------------------------------- ar cru libfoo.a foo1.o foo2.o foo3.o ulmranlib libfoo.a ar cru libbar.a bar1.o bar2.o bar3.o ulmranlib libbar.a ------------------------------------------------------------------------------ - In `notes.txt` give _short_ answers to these questions. Just assume you would post the answer on stackoverflow, so keep it short, simple and essential (or assume you have to give the answer in an oral exam): - Why do you get an linker error when you try this ---- CODE (type=txt) ------------------------------------------------------- ulmld -o xtest xtest.o libfoo.a libbar.a ---------------------------------------------------------------------------- - In the __question on stackoverflow__ two possibilities for linkage are given. One was that circular dependencies can be handled with ---- CODE (type=txt) ------------------------------------------------------- ulmld -o xtest xtest.o libfoo.a libbar.a libfoo.a ---------------------------------------------------------------------------- Why is this not working here? - Is the following working? ---- CODE (type=txt) ------------------------------------------------------- ulmld -o xtest xtest.o libfoo.a libbar.a libfoo.a libbar.a ---------------------------------------------------------------------------- And are we closer to a working solution? How can this be extended so that we finally have a working solution? - How would you rank the answers given on stackoverflow? And why? I had no good idea about how to make an exercise for the following. But the most important things in life you don't learn because you were asked about them in an exercise. So just do it for fun (and don't take the "RTFM" serious: I just want to prepare you to the slang used by coders in the wild, and I think it is funny): In the __question on stackoverflow__ the other solution was based on using the linker options `--start-group` and `--end-group`. __RTFM__ of __GNU ld__ to find out what they are meaning. These options are also supported by the ULM linker. So try this: ---- CODE (type=txt) ----------------------------------------------------------- ulmld -o xtest xtest.o --start-group libfoo.a libbar.a --end-group -------------------------------------------------------------------------------- and also this ---- CODE (type=txt) ----------------------------------------------------------- ulmld -o xtest xtest.o -\( libfoo.a libbar.a -\) -------------------------------------------------------------------------------- :links: `gcc` -> https://gcc.gnu.org shared libraries -> https://en.wikipedia.org/wiki/Library_(computing)#Shared_libraries Dynamic-link libraries \(DLLs\) -> https://en.wikipedia.org/wiki/Dynamic-link_library Static Linking - where did it go -> https://blogs.oracle.com/solaris/static-linking-where-did-it-go-v2 BSD ranlib -> https://man7.org/linux/man-pages/man1/ranlib.1.html GNU ranlib -> https://man7.org/linux/man-pages/man1/ranlib.1.html ranlib on wikipedia -> https://en.wikipedia.org/wiki/Ar_(Unix) question on stackoverflow -> https://stackoverflow.com/questions/9380363/resolving-circular-dependencies-by-linking-the-same-library-twice GNU ld -> https://linux.die.net/man/1/ld RTFM -> https://en.wikipedia.org/wiki/RTFM