Tracking down Circular Dependencies in Static Libraries

The GNU linker has some trouble when you present it with multiple library archives that depend upon each other. Libraries with symbols resolved in other libraries must be presented earlier on the command line. You can work around this with a command line argument:

"--start-group", "--end-group", aternatively "-(" "-)"

See the man page for LD for more info

Unfortunately this argument comes with the following little warning:

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 particular case I was dealing with was the havok version 6 libraries on linux. I was advised that there may be way to link them but hadn’t been worked out. In order to test this theory I hacked together a little bit of ruby to show library dependencies. I feel this may be of some use to someone else so I present it here:

require 'find'

$symbs = {}
$archives = []

class Archive
    attr_reader :name, :symbs, :depends, :undef
    def initialize name
        @name = name
        @symbs = {}
        @undef = {}
        @depends = Hash.new(0)
    end

    def add_definition loc, name
        @symbs[name] = loc
        $symbs[name] = self
    end

    def add_undefined name
    @undef[name] = 0
    end

    def resolve_undefined
        @undef.each do |k,v|
            archive = $symbs[k]
           if not archive or archive == self then
                next
            end
            @undef[k] = archive
            @depends[archive] = @depends[archive] + 1
        end
    end
end

Find.find('.') do |path|
    next if not /.a$/.match(path)

    io = IO.popen("nm #{path}")
    archive = Archive.new(path)
    $archives << archive
    while (str = io.gets) do
        case str
        when /\w+\.a/
            archive = Archive.new(str)
            puts "archive: #{str}"
        when /[A-F0-9]+ [A-Za-z] \w+/
            parts = str.split
            archive.add_definition parts[0], parts[2]
        when /\s+U\s+\w+/
            archive.add_undefined str.split[1]
        end
   end
   puts "processed #{path}, #{archive.symbs.count} defined, #{archive.undef.count} undefined"
end

$archives.each do |archive|
    archive.resolve_undefined
end

$archives.sort! {|a,b| a.depends.count <=> b.depends.count }

puts "dependency list:"
$archives.each do |archive|
    puts "#{archive.name}: #{archive.depends.count}"
    archive.depends.each do |depend,count|
        puts "    #{depend.name}: #{count}"
    end
end

The final solution was to simply remove the object files from the static libraries and put them into a single combined library:

rm *.o
find . -name \*.a -exec ar x {} \;
ar rcs libHavok.a *.o
ranlib libHavok.a
rm *.o