Why does the order in which libraries are linked sometimes cause errors in GCC?

Question

Why does the order in which libraries are linked sometimes cause errors in GCC?

Tavia

See also now #7826948 -- TLDR gcc changed to more-strict behavior (relatively) recently. – Shipyard

Answer 1

_{(See the history on this answer to get the more elaborate text, but I now think it's easier for the reader to see real command lines).}

---

Common files shared by all below commands

// a depends on b, b depends on d
$ cat a.cpp
extern int a;
int main() {
  return a;
}

$ cat b.cpp
extern int b;
int a = b;

$ cat d.cpp
int b;

Linking to static libraries

$ g++ -c b.cpp -o b.o
$ ar cr libb.a b.o
$ g++ -c d.cpp -o d.o
$ ar cr libd.a d.o

$ g++ -L. -ld -lb a.cpp # wrong order
$ g++ -L. -lb -ld a.cpp # wrong order
$ g++ a.cpp -L. -ld -lb # wrong order
$ g++ a.cpp -L. -lb -ld # right order

The linker searches from left to right, and notes unresolved symbols as it goes. If a library resolves the symbol, it takes the object files of that library to resolve the symbol (b.o out of libb.a in this case).

Dependencies of static libraries against each other work the same - the library that needs symbols must be first, then the library that resolves the symbol.

If a static library depends on another library, but the other library again depends on the former library, there is a cycle. You can resolve this by enclosing the cyclically dependent libraries by -( and -), such as -( -la -lb -) (you may need to escape the parens, such as -\( and -\)). The linker then searches those enclosed lib multiple times to ensure cycling dependencies are resolved. Alternatively, you can specify the libraries multiple times, so each is before one another: -la -lb -la.

Linking to dynamic libraries

$ export LD_LIBRARY_PATH=. # not needed if libs go to /usr/lib etc
$ g++ -fpic -shared d.cpp -o libd.so
$ g++ -fpic -shared b.cpp -L. -ld -o libb.so # specifies its dependency!

$ g++ -L. -lb a.cpp # wrong order (works on some distributions)
$ g++ -Wl,--as-needed -L. -lb a.cpp # wrong order
$ g++ -Wl,--as-needed a.cpp -L. -lb # right order

It's the same here - the libraries must follow the object files of the program. The difference here compared with static libraries is that you need not care about the dependencies of the libraries against each other, because dynamic libraries sort out their dependencies themselves.

Some recent distributions apparently default to using the --as-needed linker flag, which enforces that the program's object files come before the dynamic libraries. If that flag is passed, the linker will not link to libraries that are not actually needed by the executable (and it detects this from left to right). My recent archlinux distribution doesn't use this flag by default, so it didn't give an error for not following the correct order.

It is not correct to omit the dependency of b.so against d.so when creating the former. You will be required to specify the library when linking a then, but a doesn't really need the integer b itself, so it should not be made to care about b's own dependencies.

Here is an example of the implications if you miss specifying the dependencies for libb.so

$ export LD_LIBRARY_PATH=. # not needed if libs go to /usr/lib etc
$ g++ -fpic -shared d.cpp -o libd.so
$ g++ -fpic -shared b.cpp -o libb.so # wrong (but links)

$ g++ -L. -lb a.cpp # wrong, as above
$ g++ -Wl,--as-needed -L. -lb a.cpp # wrong, as above
$ g++ a.cpp -L. -lb # wrong, missing libd.so
$ g++ a.cpp -L. -ld -lb # wrong order (works on some distributions)
$ g++ -Wl,--as-needed a.cpp -L. -ld -lb # wrong order (like static libs)
$ g++ -Wl,--as-needed a.cpp -L. -lb -ld # "right"

If you now look into what dependencies the binary has, you note the binary itself depends also on libd, not just libb as it should. The binary will need to be relinked if libb later depends on another library, if you do it this way. And if someone else loads libb using dlopen at runtime (think of loading plugins dynamically), the call will fail as well. So the "right" really should be a wrong as well.

Peg

I've just found this useful, but I came within a fraction of downvoting myself. I've just had a link repeatedly fail for seemingly no reason, only to discover by accident that changing the order of static libraries fixes it. Reading that "There is no requirements on the linking order of object files or dynamic libraries." just seems wrong. Fortunately I read on and came to realise that its accurate - that line doesn't mention static libraries, and you address those later - but it's very easy to be misled by that first line. – Beetlebrowed

Repeat until all symbols resolved, eh - you'd think they could manage a topological sort. LLVM has 78 static libraries on it's own, with who-knows-what dependencies. True it also has a script to figure out compile/link options - but you can't use that in all circumstances. – Beetlebrowed

Great post Johannes, thanks. I had issues with static library order - the requirements for ordering are the opposite of what I expected! From the ld manpage: "The linker will search an archive only once, at the location where it is specified on the command line. If the archive defines a symbol which was undefined in some object which appeared before the archive on the command line, the linker will include the appropriate file(s) from the archive. However, an undefined symbol in an object appearing later on the command line will not cause the linker to search the archive again." – Ilex

@Steve that's what the programs lorder + tsort do. But sometimes there is no order, if you have cyclic references. Then you just have to cycle through the libraries list until everything is resolved. – Peg

@Johannes - Determine the maximal strongly connected components (e.g. Tarjans algorithm) then topologically sort the (inherently non-cyclic) digraph of components. Each component can be treated as one library - if any one library from the component is needed, the dependency cycle(s) will cause all libraries in that component to be needed. So no, there really is no need to cycle through all the libraries in order to resolve everything, and no need for awkward command-line options - one method using two well-known algorithms can handle all cases correctly. – Beetlebrowed

@Steve Unfortunately I haven't done anything with those algorithms. But I would like to have an easy to use LD commandline option with those methods you mention too. Perhaps you can send your ideas to the respective GNU mailing lists? – Peg

@Johannes - not really my idea. I first read about it from a Dr. Dobbs article someone wrote about some other kind of programming tool (IIRC, the topological sort was a performance optimisation, but the dependency graphs couldn't be guaranteed acyclic), and it didn't seem special then. I assumed GNU had chosen to reject this kind of approach, perhaps for religious reasons. After all, there are other linkers that must be doing this or something similar - I haven't invented anything clever or original here. Still, it can't hurt to write an e-mail - I'll sort something out soon. – Beetlebrowed

I would like to add one important detail to this excellent answer: Using "-( archives -)" or "--start-group archives --end-group" is the only sure-fire way of resolving circular dependencies, since each time the linker visits an archive, it pulls in (and registers the unresolved symbols of) only the object files that resolve currently unresolved symbols. Because of this, CMake's algorithm of repeating connected components in the dependency graph may occasionally fail. (See also Ian Lance Taylor's excellent blog post on linkers for more detail.) – Polythene

Hi, Can I ask how did you generate the beautiful dependency art ?( the " +- prog.o -----+" stuff) thanks. – Chlorophyll

@Chlorophyll I suspect a text editor was used. Two (one organic and one software). Other than that, look at search.cpan.org/~tels/Graph-Easy/bin/graph-easy#ASCII_output – Firebreak

Your answer helped me to resolve my linking errors and you have very clearly explained HOW to avoid getting into trouble, but do you have any idea WHY was it designed to work this way? – Shani

Fantastic write up: it gets an up-vote from me. I would add to the section on resolving cyclic dependencies, I'll leave it to the original poster if they wish to modify, that when passing the --start-group and --end-group options using gcc, you must precede with -Wl,<option> as in -Wl,--start-group <archives> -Wl,--end-group. It is mentioned in the manual page which is referenced, but a quick mention here is helpful too. – Considered

"dynamic librarries" typo. I think the order can matter for dynamic libraries if you use an option like --as-needed (the default in ubuntu IIRC) and the libraries are not linked to everything they depend on (--allow-shlib-undefined), but that's probably too rare for a general introduction. – Garlan

MSVC does not have such order dependencies, I find this very annoying about GCC. Especially with static libraries: The only reason to do order dependent linking is because of potential ODR violations, but the linker shouldn't support that anyway since it's illegal. Read in all static libraries specified at the command line, create a pool of symbols, and do lookups from that. – Widthwise

Hmm, I'm sure sure that your statement -l "leaves the compiler open to choose the dynamic libA.so and libB.so variant, if available" is still correct. From the GCC manual: The linker searches a standard list of directories for the library, which is actually a file named lib<library>.a. The linker then uses this file as if it had been specified precisely by name. – Ethelyn

There is no requirement on the linking order of ... dynamic libraries. This statement is fundamentally false. Yes, due to a quirk in the behaviour of ELF linkers, you may get away with incorrect ordering for dynamic libraries, but wrong order is still fundamentally wrong, and will bite, if you use the same wrong order with, say, a Windows-PE linker, which does not exhibit the ELF quirk. – Apodosis

@keith thanks, wasn't aware. What is that quirk you refer to? It sounds like something fundamental. Can you please link to more information? I could imagine that the order might influence the order of the resulting DT_NEEDED entries which might result in different symbol resolution order by ld.so at runtime. I can't remember whether I checked up that issue when I created the answer. – Peg

@Johannes, GNU ld works, like most unix linkers, in a single pass. If a symbol isn't already known to be required, to satisfy an unresolved reference, at the time when its providing library is scanned, then it will not be mapped into the linked image; there is no going back later, to rescan a library, (unless it is specifically included within a -( ... -) group). The "quirk", when linking ELF, is that dynamic libraries do appear to be arbitrarily rescanned, without grouping, so incorrect ordering isn't punished; for non-ELF, (e.g. Windows-PE), wrongly ordered DLLs are punished. – Apodosis

@KeithMarshall ah, I see. I will try this with the mingw cross compiler later to see whethether that's true. Why is it considered a quirk that it works when using ELF? I mean, it's single-pass, OK, but the design of ELF specifically binds symbols only at dynamic link time (unless prelinking is used, which is out of the question's scope I think). So how could there be possibly be an "incorrect" ordering with ELF that makes linking fail the way you describe? – Peg

I also noted that programs that depend on unspecified behavior can be affected by linking order (by unspecified behavior, I meant the behavior as far as the C++ Standard is concerned, since the question is tagged C++). I will add some more text to clarify. That includes changing the order of the SO-files which will change breath-first iteration at dynamic link time and so will potentially make symbols resolve differently. I also removed the note that such effects only show up in "defective" programs - too strong, and expanded on the description of link order of so files. Please checkup. – Peg

@Johannes, it's "incorrect" ordering insofar as it violates the "correct" ordering requirement, as documented for the ld component of GUN binutils; it's a "quirk" w.r.t. this required ld order that the design of ELF is such that it doesn't care anyway, so "correct" order w.r.t. ld documented behaviour isn't enforced. This causes complacency about ld-correct ordering among developers who primarily target ELF; I've lost count of the number of times project porting from Linux to MS-Windows has resulted in questions on MinGW-Users ML, because "broken" link order prevents DLL linking. – Apodosis

@keith can you please link to where LD documents such ordering? I now am of the opinion that trying to list those libraries in an order that could satisfy some requirements is plain wrong: the libraries themself can and must state their dependencies in their own list of dependencies. When linking the executable, those dependencies should not be listed again: it would make no sense. Only if the binary built does itself depend on those libraries. This becomes more clear with more recent LD versions that use "--as-needed" by default. – Peg

The discrepancy between dynamic shared libraries and static libraries is because the dynamic libraries are already linked and have their dependencies sorted out. – Peg

Imagine the other way around: You link against shared lib X which in one version happens to require shared lib Y. If it doesn't itself link to Y, but relies on the executable, you can't anymore replace X with another version of X that instead requires a lib Z instead of or in addition to Y. But then you have lost a pretty big advantage of what ELF shared libraries provide. – Peg

@Johannes, info ld Invocation -> Options, para '-l NAMESPEC": "The linker will search an archive only once, at the location where it is specified on the command line. If the archive defines a symbol which was undefined in some object which appeared before the archive on the command line, the linker will include the appropriate file(s) from the archive. However, an undefined symbol in an object appearing later on the command line will not cause the linker to search the archive again." There is no suggestion that this applies differently to static and dynamically linked libraries. – Apodosis

@Johannes, how can you possibly lose a feature of ELF, on a platform which isn't ELF? You simply cannot exploit a feature of ELF on a PE-coff platform, such as MS-Windows, where DLLs, (or their respective import libraries), are subject to identically the same ordering constraints as static libraries. – Apodosis

@keith ok. My answer doesn't state things about PE DLL files. It is about ELF files. It is entirely possible that dll files work similar like archives on linux on that regard, I am not experienced with them (and I don't think that quote of the infopage of LD is about ELF files. They are not archives that contain files). Since there isn't a meaningful ordering for ELF files (or at least you haven't given me a link that shows one), I don't understand how you can say that there could be an "incorrect" order used when linking. – Peg

@Johannes, I see you qualified your answer, to clarify that the dynamic linking aspects are specific to ELF. However, it still seems to do nothing to discourage developers from writing degenerate linking commands, such as gcc -lshared-foo bar.o -o bar, which will result in undefined reference errors on non-ELF platforms such as MS-Windows, if shared-foo.dll is needed. Surely, it is better to encourage usage such as gcc bar.o -lshared-foo -o bar, which should work equally well on both ELF and non-ELF platforms. – Apodosis

@Johannes, and as my final word on the subject, if developers can be encouraged to adopt the gcc bar.o -lshared-foo -o bar style, (which is consistent with the required ordering specified in ld documentation), it may just save them from being severely berated, when they complain for the gadzillionth time that gcc -lshared-foo bar.o -o bar doesn't work on MS-Windows; just because it fortuitously works on Linux doesn't make it automatically "right": it isn't best practice, nor even good practice. – Apodosis

@KeithMarshall gcc -lshared-foo bar.o is incorrect if bar.o depends on shared-foo. There are no dependencies between the shared libraries according to my answer (you can mix the -lsharedfoo anyway you like), but there may be dependencies of the .o or .a files to a shared library. Then you have to put the bar.o file before. Not doing that even breaks on ELF systems on recent distributions (with --as-needed). – Peg

@KeithMarshall i completely rewrote my answer because it started to become messy.. – Peg

What happens when libd.a has a file scope c++ object that needs to be initialized before libb.a. Listing libd.a first should ensure the static initializer runs first, but that leads into the wrong order category (though it is the right order for static initialization). – Gauntlett

@Gauntlett you are in dangerous land here. Maybe try the begin and end group flags and use the whole-archive flag. Also try the init_priority attribute at gcc.gnu.org/onlinedocs/gcc/… . Global object initializations best should not have side effects. At language level, I recommend declaring them as static locals and returning them by reference. – Peg

Answer 2

The GNU ld linker is a so-called smart linker. It will keep track of the functions used by preceding static libraries, permanently tossing out those functions that are not used from its lookup tables. The result is that if you link a static library too early, then the functions in that library are no longer available to static libraries later on the link line.

The typical UNIX linker works from left to right, so put all your dependent libraries on the left, and the ones that satisfy those dependencies on the right of the link line. You may find that some libraries depend on others while at the same time other libraries depend on them. This is where it gets complicated. When it comes to circular references, fix your code!

Modestomodesty

Is this something with only gnu ld/gcc? Or is this something common with linkers? – Geibel

Apparently more Unix compilers have similar issues. MSVC isn't entirely free of these issues, eiher, but they don't appear to be that bad. – Oxblood

The MS dev tools don't tend to show these issues as much because if you use an all-MS tool chain it ends up setting up the linker order properly, and you never notice the issue. – Fashion

The MSVC linker is less sensitive to this issue because it will search all libraries for an unreferenced symbol. Library order still can affect which symbol gets resolved if more than one library have the symbol. From MSDN: "Libraries are searched in command line order as well, with the following caveat: Symbols that are unresolved when bringing in an object file from a library are searched for in that library first, and then the following libraries from the command line and /DEFAULTLIB (Specify Default Library) directives, and then to any libraries at the beginning of the command line" – Digestant

"... smart linker ..." - I believe it is classified as a "single pass" linker, not a "smart linker". – Gauntlett

@jww, I would imagine ``single pass smart linker'' may be more accurate. A single pass non-smart linker would not perform the same way, n'est pas? From the SmartLinker book (ee-classes.usc.edu/ee459/library/documents/SmartLinker.pdf): "The Linker is a smart linker, i.e. it will only link those objects that are actually used by your application." How many passes it takes to do that does not change whether it is a smart linker or not. – Modestomodesty

Re “A single pass non-smart linker would not perform the same way”: The algorithm is simple: For each module in a library on the link command line, if the module satisfies a currently pending reference, include the module in the output file being constructed. Otherwise, do not. Likely the symbols in an unselected module are never entered into the linker’s lookup table at all, so they are not tossed out from it. – Freak

@Geibel Not all linkers, I prepared a Makefile demo on a Mac that I was going to show to students in a Linux lab. Just to be sure, before the class, I tried it on the Linux computers and was getting undefined references. I knew about this problem so it was easy to fix. – Nuggar

@PhilippeCarphin The macOS dynamic linker, which produces files with the extension .dylib, could search anywhere on the system for symbols! Holy smokes! That is one strange beast, it is not simple like GNU ld. On LInux, I have since switched to the Modern Linker - it does linking in parallel! Super fast! – Modestomodesty

Answer 3

Here's an example to make it clear how things work with GCC when static libraries are involved. So let's assume we have the following scenario:

• myprog.o - containing main() function, dependent on libmysqlclient
• libmysqlclient - static, for the sake of the example (you'd prefer the shared library, of course, as the libmysqlclient is huge); in /usr/local/lib; and dependent on stuff from libz
• libz (dynamic)

How do we link this? (Note: examples from compiling on Cygwin using gcc 4.3.4)

gcc -L/usr/local/lib -lmysqlclient myprog.o
# undefined reference to `_mysql_init'
# myprog depends on libmysqlclient
# so myprog has to come earlier on the command line

gcc myprog.o -L/usr/local/lib -lmysqlclient
# undefined reference to `_uncompress'
# we have to link with libz, too

gcc myprog.o -lz -L/usr/local/lib -lmysqlclient
# undefined reference to `_uncompress'
# libz is needed by libmysqlclient
# so it has to appear *after* it on the command line

gcc myprog.o -L/usr/local/lib -lmysqlclient -lz
# this works

Carefree

Answer 4

If you add -Wl,--start-group to the linker flags it does not care which order they're in or if there are circular dependencies.

On Qt this means adding:

QMAKE_LFLAGS += -Wl,--start-group

Saves loads of time messing about and it doesn't seem to slow down linking much (which takes far less time than compilation anyway).

Deeplaid

it works because of /usr/bin/ld: missing --end-group; added as last command line option – Fickle

Though looks like it does not always work because of missing --end-group. – Gallant

It works, but makes the linker a dumb linker, it just links everything. – Modestomodesty

Answer 5

Another alternative would be to specify the list of libraries twice:

gcc prog.o libA.a libB.a libA.a libB.a -o prog.x

Doing this, you don't have to bother with the right sequence since the reference will be resolved in the second block.

Tarra

Answer 6

A quick tip that tripped me up: if you're invoking the linker as "gcc" or "g++", then using "--start-group" and "--end-group" won't pass those options through to the linker -- nor will it flag an error. It will just fail the link with undefined symbols if you had the library order wrong.

You need to write them as "-Wl,--start-group" etc. to tell GCC to pass the argument through to the linker.

Tedder

Answer 7

You may can use -Xlinker option.

g++ -o foobar  -Xlinker -start-group  -Xlinker libA.a -Xlinker libB.a -Xlinker libC.a  -Xlinker -end-group 

is ALMOST equal to

g++ -o foobar  -Xlinker -start-group  -Xlinker libC.a -Xlinker libB.a -Xlinker libA.a  -Xlinker -end-group 

Careful !

1. The order within a group is important ! Here's an example: a debug library has a debug routine, but the non-debug library has a weak version of the same. You must put the debug library FIRST in the group or you will resolve to the non-debug version.
2. You need to precede each library in the group list with -Xlinker

Urethra

Answer 8

I have seen this a lot, some of our modules link in excess of a 100 libraries of our code plus system & 3rd party libs.

Depending on different linkers HP/Intel/GCC/SUN/SGI/IBM/etc you can get unresolved functions/variables etc, on some platforms you have to list libraries twice.

For the most part we use structured hierarchy of libraries, core, platform, different layers of abstraction, but for some systems you still have to play with the order in the link command.

Once you hit upon a solution document it so the next developer does not have to work it out again.

My old lecturer used to say, "high cohesion & low coupling", it’s still true today.

Graniela

Answer 9

Link order certainly does matter, at least on some platforms. I have seen crashes for applications linked with libraries in wrong order (where wrong means A linked before B but B depends on A).

Freeborn

Answer 10

ld : linker daemon has been around since 1990's and it's not a program we spend a lot of time with because the automake/cmake makefile recipes are pretty easy to obtain most behaviour.

It has a LDFLAGS option known as --start-group or -(

-( archives -)

--start-group archives --end-group 

This allows you to search more than once for symbols while recursing through the specific archives looking for symbols.

This is from the linker manual:

--start-group archives --end-group

The archives should be a list of archive files. They may be either explicit file names, or `-l' options. The specified archives are searched repeatedly until no new undefined references are created. Normally, an archive is searched only once in the order that it is specified on the command line. If a symbol in that archive is needed to resolve an undefined symbol referred to by an object in an archive that appears later on the command line, the linker would not be able to resolve that reference. By grouping the archives, they all be searched repeatedly until all possible references are resolved. Using this option has a significant performance cost. It is best to use it only when there are unavoidable circular references between two or more archives.

The linker daemon is like a spaghetti colander, a bunch of symbols arrive at the colander walls and poke through the holes, and the linker must track all symbols and connect together all the symbols by address linkage. If it misses some, the program will crash.

Here's what you need to know about static versus dynamic libraries When linking symbols for static libraries, ld starts from left to right and MAKES ONE PASS through all symbol tables. If you want to resolve dependency loops then you can add the same archive into the linker archive objects list more than once.

When dealing with dynamic libraries, all symbols must be resolved by the dynamic libraries so nothing gets missed.

Therefore, the one time behaviour will fail is when some symbols are static and the dynamic symbols will not be around during the single pass.

The answer then, is place the static libraries TO THE LEFT of the dynamic libraries in the make recipe.

Higgs

I like the substance of your answer and the emphasis on the one-pass nature of the process (by default), but a couple of historical notes: the ld command has been around since at least the first version of Unix, so we are talking early 1970s, not 90s. Also, it is not a daemon (a persistent background process); that seems like a backronym. While I haven't found any sources to prove it, my guess is that "ld" stands for "loader", a term that was sometimes used interchangeably with "linker" back then, and is indeed present in the v1 ld manpage. – Powerless

Answer 11

It matters where you put your files for a linker to resolve.

It is a general rule that you put files where symbol is referenced BEFORE file where symbol is defined.

To understand the reason of error you have to understand how linker works:

• All files passed to linker processed from left to right

• Linker collects undefined symbols from files to the pool of undefined symbols

• If object from archive doesn’t resolve any symbols from pool of undefined symbols, then it dropped

In a case:

gcc -o libfunc2.so -shared -fPIC -lfunc1 func2.o

We put archive library where symbol show1() is defined before object file func2.o where it is referenced. So libfunc1.a doesn't resolve any symbols and is dropped.

And from GCC -l library option:

It makes a difference where in the command you write this option; the linker searches and processes libraries and object files in the order they are specified.

Thus, foo.o -lz bar.o

searches library z after file foo.o but before bar.o. If bar.o refers to functions in library z, those functions may not be loaded.

Foretop