Resolving circular dependencies by linking the same library twice?

Question

We have a code base broken up into static libraries. Unfortunately, the libraries have circular dependencies; e.g., libfoo.a depends on libbar.a and vice-versa.

I know the "correct" way to handle this is to use the linker's --start-group and --end-group options, like so:

g++ -o myApp -Wl,--start-group -lfoo -lbar -Wl,--end-group

But in our existing Makefiles, the problem is typically handled like this:

g++ -o myApp -lfoo -lbar -lfoo

(Imagine this extended to ~20 libraries with complex interdependencies.)

I have been going through our Makefiles changing the second form to the first, but now my co-workers are asking me why... And other than "because it's cleaner" and a vague sense that the other form is risky, I do not have a good answer.

So, can linking the same library multiple times ever create a problem? For example, could the link fail with multiply-defined symbols if the same .o gets pulled in twice? Or is there any risk we could wind up with two copies of the same static object, creating subtle bugs?

Basically, I want to know if there is any possibility of link-time or run-time failures from linking the same library multiple times; and if so, how to trigger them. Thanks.

Keelung

The only problem I can think of is when you manage to link with two different versions of same library. That's hard to do and (IMO) is unlikely to occur on linux. Also, only 20 libraries doesn't look like much. Is it worth walking through makefiles? You could spend that time doing something else. – Swartz

This problem just goes away if you fix your libraries to not have circular dependencies. – Badge

I presume removing circular dependencies by examining and breaking up the libraries isn't feasible? Because that'd be the cleanest way – Maineetloire

@Mark - Not easily done, because it is a non-trivial legacy code base and because some useful OOP patterns create circular dependencies naturally. – Keelung

@Swartz - I cannot think of any specific problem, either, which is why I am asking the question. – Keelung

A downside to the first form is that it forces the linker to include all the objects in the libraries to be added to your binary. Whether this is a problem for you depends on how sensitive you are to binary size, but if your application doesn't actually use most of the code in your libraries, then linking using the first form can make your binary much bigger. The second form does look messy, and is a sign of poor library design, but is probably the most efficient way to deal with a bad situation from the binary size aspect. – Labaw

Answer 1

All I can offer is a lack of counter-example. I've actually never seen the first form before (even though it's clearly better) and always seen this solved with the second form, and haven't observed problems as a result.

Even so I would still suggest changing to the first form because it clearly shows the relationship between the libraries rather than relying on the linker behaving in a particular way.

That said, I would suggest at least considering if there's a possibility of refactoring the code to pull out the common pieces into additional libraries.

Badge

Thanks, Mark. Although I do find it amusing that half of the comments on my question say "Fix your codebase!" and the other half say "Why are you tampering with a working codebase?" :-) – Keelung

The first form would introduce a performance cost as the linker try to find symbols repeated across all listed libraries. see this: https://mcmap.net/q/64297/-why-does-the-order-in-which-libraries-are-linked-sometimes-cause-errors-in-gcc – Alderney

The first form is also only working for GNU ld and is thus not a portable solution. – Brennen

Answer 2

The problem with

g++ -o myApp -lfoo -lbar -lfoo

is that there is no guarantee, that two passes over libfoo and one pass over libbar are enough.

The approach with Wl,--start-group ... -Wl,--end-group is better, because more robust.

Consider the following scenario (all symbols are in different object-files):

• myApp needs symbol fooA defined in libfoo.
• Symbol fooA needs symbol barB defined in libbar.
• Symbol barB needs symbol fooC defined in libfoo. This is the circular dependency, which can be handled by -lfoo -lbar -lfoo.
• Symbol fooC needs symbol barD defined in libbar.

To be able to build in the case above, we would need to pass -lfoo -lbar -lfoo -lbar to the linker. Why?

1. The linker sees libfoo for the first time and uses definitions of symbol fooA but not fooC, because so far it doesn't see a necessity to include also fooC into the binary. The linker however starts to look for definition of barB, because its definition is needed for fooA to function.
2. The linker sees -libbar, includes the definition of barB (but not barD) and starts to look for definition of fooC.
3. The definition of fooC is found in libfoo, when it processed for the second time. Now it becomes evident, that also the definition of barD is needed - but too late there is no libbar on the command line anymore!

The example above can be extended to an arbitrary dependency depth (but this happens seldom in real life).

Thus using

g++ -o myApp -Wl,--start-group -lfoo -lbar -Wl,--end-group

is a more robust approach, because linker passes as often over the library group as needed - only when a pass didn't change the symbol table will the linker move on to the the next library on the command line.

There is however a small performance penalty to pay: in the first example -lbar were scanned once more compared with the manual command line -lfoo -lbar -lfoo. Not sure whether it is worth mentioning/thinking about through.

Fikes

is the --start-group ... --end-group just a convenience switch, or does it deal with the circular dependencies faster, by cacheing the .o files or the symbol tables of the whole group? I mean, if I turn the g++ -o myApp -lfoo -lbar -lfoo -lbar -lfoo into a --start-group ... --end-group do I expect the linker to scan the lfoo and lbararchives just once each? – Oar

It's not a convenience switch because it will continue to work, even if more cycles are added in the code. The handwritten command line will break if barD suddenly needs fooE, even though dependency-wise, "nothing" has changed, as it's still foo and bar depending on each other. To clarify, simply pulling in additional symbols from libraries you already link against might break the build. – Shirker

Answer 3

Since it is a legacy application, I bet the structure of the libraries is inherited from some arrangement which probably does not matter any more, such as being used to build another product which you no longer do.

Even if still structural reasons remain for the inherited library structure, almost certainly, it would still be acceptable to build one more library from the legacy arrangement. Just put all the modules from the 20 libraries into a new library, liballofthem.a. Then every single application is simply g++ -o myApp -lallofthem ...

Pernas