11

Are there any decent tools to determine the optimal static link order with g++ under Linux? I'm familiar with the general issues, including (if necessary) the use of repeated references to a single library or --start-group and --end-group to resolve circular dependencies, but what I'd like, if possible, is a tool that will take a bunch of .a files and spit out a good static link order for them, repeating libraries if necessary, while keeping the repetition to a minimum.

Background: I'm working on a project with around 800K lines of inherited c++ code, and trying to refactor it into smaller, more manageable chunks. Some of the existing files are huge monoliths - today I've been wrestling with a single 34K line .h file that defined 113 classes and structs. Many of the classes were defined almost entirely inline in the .h file. As I split this up into smaller chunks, and migrate some of the implementation code into .cpp files, the required link order on Linux keeps changing. That's probably because every library that included the .h file used to compile its own implementation of whatever classes it needed, and now they are having to link to a common implementation in a single library file. Long-term we'll probably reorganize some of the classes into different libraries, and break some of the dependency chains, but right now the dependencies are pretty tangled, and I'm trying to minimize the perturbations to the code that could change behavior. I'd prefer not to have to keep manually figuring out the right link order every time it changes. Suggestions?

dewtell
  • 1,402
  • 10
  • 14

2 Answers2

4

I'm not aware of one offhand, but you could implement one yourself. Just use nm to get a list of symbols from each static library, use this to build a dependency graph, then perform a topological sort over the graph for the proper link order.

Alternately, use partial links (ld -r) instead of static libraries. Since this outputs a merged .o file, your final link can declare the libraries in any order, and they'll all be linked properly. The downside is that the linker won't be able to discard unused source files, since they're already linked into monolithic files before usage data is available (you can workaround this by passing -ffunction-sections -fdata-sections during compilation and -Wl,--gc-sections on final link, although this may impact how long it takes to compile)

bdonlan
  • 224,562
  • 31
  • 268
  • 324
  • 1
    I've thought of that, but the problem is a bit trickier than that. Topological sort works if you need to wait for everyone who calls you before you get included. But that's not required here: if library A has a symbol a that needs a symbol b from library B, it's ok (and indeed, it may be necessary) for B to precede A in the link order as long as there is someone earlier in the order who also requires b. I could probably work up a reasonable algorithm, but it would take time, and meanwhile there's work with deadlines to be done. So I'd prefer a battle-tested solution that's already there. – dewtell Jun 22 '11 at 04:52
  • @dewtell: There may be cases where this approach won't work, but are you certain your code-base is one of them? – Andrew Aylett Jul 05 '11 at 14:05
  • @Andrew - pretty sure. Based on the .h files inclusions, there's plenty of cases where file1a in lib1 references a symbol defined in file2a in lib2, while file2b in lib2 references a symbol defined in file1b in lib1. – dewtell Jul 09 '11 at 21:12
1

You could use shared libraries instead of static and compile with -fPIC option.

Community
  • 1
  • 1
Andrew Selivanov
  • 1,306
  • 15
  • 22
  • This isn't a good idea for us in the short run, as it would radically change how we ship and install the program, and introduce a whole new source of bugs. In the long run, it's something we could look at, but probably not just to solve this particular issue. – dewtell Jul 01 '11 at 20:19