I can't provide the .o files exhibiting this problem, hence I have to just
give my analysis. We have a case where there are big object files containing
many of such relocations:
000000030328 042c00000027 R_IA64_DIR64LSB 0000000000000000 .text + 2ee51
000000030330 042c00000027 R_IA64_DIR64LSB 0000000000000000 .text + 2ed41
000000030338 042c00000027 R_IA64_DIR64LSB 0000000000000000 .text + 2ee41
Thousands of them.
The special thing here is, many relocations against the same symbol (here
a local pseudo symbol for .text) but differing addends. The ia64 linker
in elfNN_ia64_check_relocs goes over all relocs, calling get_dyn_sym_info()
on each one. For local symbols (as is the case here) this collects a linked
list of elfNN_ia64_dyn_sym_info entries _for each addend_ without duplicates.
As this is a linked list just checking for duplicates is O(N^2) in the number
of such relocs.
The above relocs specifically where in the .rela.debug_ranges section, so
in this case it's debug info which leads to ld breaking down.
Linking the specific .o files in question needs many hours it seems (I wasn't
yet patient enough to really leave it running through the end), but in gdb
one can see that elfNN_ia64_check_relocs doesn't finish for a long time.
The O(N^2) is quite obvious, but I don't know yet if that's the only cause for
the huge reported link time.
--
Summary: ld slow with many local relocs (O(N^2) in
get_dyn_sym_info)
Product: binutils
Version: 2.17 (HEAD)
Status: NEW
Severity: normal
Priority: P2
Component: ld
AssignedTo: unassigned at sources dot redhat dot com
ReportedBy: matz at suse dot de
CC: bug-binutils at gnu dot org
GCC target triplet: ia64-linux
http://sourceware.org/bugzilla/show_bug.cgi?id=2442
------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.
_______________________________________________
bug-binutils mailing list
bug-binutils@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-binutils
