This is the mail archive of the mailing list for the binutils project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] MIPS support for --hash-style=gnu

I am tasked with reducing the time spent in the interpreter/loader at program start time for a very large, multi-platform, multi-architecture, legacy system (25+Mloc, 2000+ DSOs, 1+M symbols).  On MIPS this loader overhead is several much larger than for other supported architectures, which is not unexpected given the lack of .gnu.hash support. [1]  Measurement shows that a principal factor for the programs most affected is the very large number of DSOs which are directly or indirectly needed -- the chief expense being the cost of successive table misses during symbol resolution.  A secondary factor is that some of the executables and DSOs have a very large number of symbols with relocations -- on MIPS these tend to run afoul of the multi-GOT mechanism which places many into secondary GOTs, resulting in unconditionally forcing their resolution at load time. [2][3][4]  At this stage in the lifecycle of this particular product, large scale architectural changes tend not to be feasible (e.g. appreciably decreasing either the number of DSOs or the number of relocations) so a more transparent solution is preferable.  (c.f. [5][6])

In order to tackle the main problem -- large numbers of needed DSOs -- some means of avoiding unprofitable (i.e. certain miss) hash table probes would help significantly.  Since code to support Bloom filtering already exists for GNU-style hash tables (DT_GNU_HASH), it seemed attractive to enable that feature for MIPS (and then also benefit from as much of the hash chain optimization as possible). [6]  As I understand it, the fundamental problem which has historically prevented this support is, briefly, that the MIPS ABI requires that the .dynsym table be sorted in a particular order, while .gnu.hash mandates a different order; this appears to have stymied at least one earlier attempt. [8]  As I am expert neither with MIPS and its many ABI oddities, nor with the implementation of the BFD linker, I have opted to take a very, very simple -- if perhaps non-optimal -- approach.  Inspired by the comment made by Richard Sandison to Hiroki Kaminaga concerning external symbol blocks [9], I chose to reuse GNU-style hash tables, only with the simple addition of a translation table to map the GNU symbol order to the MIPS symbol order.  The MIPS .dynsym table proper continues to be completely identical: its sort order and content are entirely unchanged.  The proposed changes also leave the output of all other targets/backends entirely unchanged (including MIPS using traditional SysV .hash).

In an attempt to avoid forward compatibility issues, a new section and related dynamic tag are proposed: .gnu.xhash and DT_GNU_XHASH.  (The "X" standing either for "extended" or as a mnemonic for "translated", as the reader prefers.)  This ensures that old binutils, glibc, and other third party code do not attempt to behave as if a traditional .gnu.hash/DT_GNU_HASH is present.  Likewise, the name of the section was chosen so that it is not a textual prefix of .gnu.hash in an attempt to preclude any insufficiently discriminating pattern from matching inadvertently (e.g. in a script parsing readelf output).

In practice, though, the .gnu.xhash section is virtually identical to .gnu.hash. [9]

	// Part 0: .gnu.xhash header
	Elf32_Word  ngnusyms;  // number of entries in chains (and xlat); dynsymcount=symndx+ngnusyms
	// Part 1: .gnu.hash header
	Elf32_Word  nbuckets;  // number of hash table buckets
	Elf32_Word  symndx;  // number of initial .dynsym entires skipped in chains[] (and xlat[])
	Elf32_Word  maskwords; // number of ElfW(Addr) words in bitmask
	Elf32_Word  shift2;  // bit shift of hashval for second Bloom filter bit
	// Part 2: .gnu.hash Bloom filter
	ElfW(Addr)  bitmask[maskwords];  // 2 bit Bloom filter on hashval
	// Part 3: .gnu.hash buckets
	Elf32_Word  buckets[nbuckets];  // indices into chains[]
	// Part 4: .gnu.hash chains
	Elf32_Word  chains[ngnusyms];  // consecutive hashvals in a given bucket; last entry in chain has LSB set
	// Part 5: .gnu.xhash translation table
	Elf32_Word  xlat[ngnusyms];  // parallel to chains[]; index into .dynsym

Parts 1 through 4 correspond exactly in layout to the traditional .gnu.hash; part 4 has slightly different semantics since the correct MIPS .dynsym index has to be first looked up in the parallel xlat table i.e. the symbol corresponding to the hashval in chain[N] is .dynsym[xlat[N]].  It is intentional that the .gnu.xhash layout contains a .gnu.hash layout as a subcomponent: it represents an attempt to reuse unchanged as much BFD and readelf code as possible.  The space cost of .gnu.xhash relative to .gnu.hash is ngnusyms+1 32 bit words.  (For time cost, the L2 cache hit from the xlat table lookup is probably atrocious, but at that point we're already about to perform a string compare which is probably going to be even more atrocious....  In any case, it's a whole lot better than SysV .hash.)

In order to reuse the maximum amount of existing code with the minimum amount of copying while also maintaining 100% backward compatibility, I chose to implement the support as a BFD ELF backend hook: record_hash_symbol().  For all platforms other than MIPS, this hook is NULL and the behaviour is to write .gnu.hash (or not) exactly as they always have done.  For MIPS, this hook is non-NULL and (when --hash-style=gnu) will output a .gnu.xhash section which the MIPS specific ELF backend then updates with a translation table to allow .gnu.xhash symbol indices to be translated to MIPS .dynsym indices at the right time during linking.  The principal changes to the common support (in bfd/elflink.c) are in bfd_elf_size_dynsym_hash_dynstr() which computes the correct size for the .gnu.[x]hash section; and in elf_renumber_gnu_hash_syms() which did the sorting for .gnu.hash.  On the ELF MIPS specific side, the main changes are to mips_elf_sort_hash_table_f(); and in the addition of the backend function _bfd_mips_elf_record_hash_symbol() with an associated new field in struct mips_elf_link_hash_entry.

In bfd_elf_size_dynsym_hash_dynstr() the code was modified as little as possible in order to keep the diff small and simple to review; the unfortunate corollary to that is that the changes are a little ugly and somewhat brittle (conditionally shifting the contents pointers along etc.)  This also to an extent dictated the layout of the .gnu.xhash section: it is essentially a .gnu.hash section with a leading ngnusyms word and a following translation table.  (The basic form of the .gnu.hash section was retained so as also to keep the readelf changes to a minimum.)

The elf_renumber_gnu_hash_syms() function no longer unconditionally renumbers the symbols.  Instead, if the backend supplies record_hash_symbol(), then that is called instead to allow it to record the offset of the translation table entry for that symbol.  The MIPS backend will then fill this in later once it has finished fiddling with the GOT(s).  I chose to pass an offset here rather than a pointer only because I wasn't entirely certain if it was architecturally acceptable to assume that the content of the section would never be replaced sometime in between (although this is not currently the case).

On the ELF MIPS side, mips_elf_sort_hash_table_f() now also outputs the final index of each symbol into the .gnu.xhash translation table as required.  This is also a bit brittle since it assumes that nothing else is going to come along and change the order yet again afterwards, but that is also true of all of the already existing MIPS backend code.

The readelf support essentially speaks for itself.  Again, it's a bit ugly since I tried to stick only to insertions and not changing existing lines, so as to make the code inspect simpler.

No changes to gold are proposed here because, if I understand correctly, there is as yet no general MIPS support in any case.

I have included the glibc changes here only as a convenience to reviewers; I will be posting to libc-alpha as well.  (It is perhaps interesting to note in passing that although --hash-style=gnu was disabled in the linker, DT_GNU_HASH support was never removed from the glibc MIPS sysdep dl-lookup.c.  This means that on MIPS the new and old hashvals are currently always both computed at runtime for every symbol.  Fortunately in practice this cost appears to be entirely negligible.  Laterally, I suspect that Jakub Jelinek had independently confirmed this insignificance and is why .hashvals never made it into .gnu.hash. [11]  I experimented with adding .hashvals as well as .gnu.xhash, but it made no appreciable difference.)

The patch is relative to binutils-2_24 (which is where I'll ultimately need it) but is equally applicable to trunk.  (The glibc patch is relative to a lightly customized 2.16 but again is equally applicable to trunk.)  As this is my first attempt at a patch for the linker, I've omitted the ChangeLog and test cases for the moment, pending feedback.  Technical and procedural criticism is gratefully welcomed.  I should very much like to thank the many who have taken the time to post on these and related subjects over the years -- I would have found even this modest attempt very difficult without the historical context.  Particular thanks are due to Michael Meeks, Jakub Jelinek, Richard Sandiford, and Hiroki Kaminaga.  Errors in comprehension and judgement are entirely my own.


P.S.  It is not entirely clear to me how xgot support does or should interact with multi-GOT. [12]  With xgot supporting about 2**32 entries, shouldn't it be the case that multiple GOTs are almost never needed?

[1]  Disable .gnu.hash on MIPS targets
[2]  MIPS Multi GOT
[3]  MIPS multi-got link support
[4]  Description of MIPS/IRIX multigot
[5]  Speeding up the dynamic linker with 100s of DSOs?
[6]  Re: OO.o / ld / -Bsymbolic patch
[7]  [PATCH] DT_GNU_HASH: ~ 50% dynamic linking improvement
[8]  [RFC][PATCH][EXPERIMENTAL] enable MIPS gnu hash (was: Re: use of gnu hash for MIPS)
[9]  Re: use of gnu hash for MIPS
[10]  Re: GNU_HASH section format
[11]  binutils/glibc .hashvals section ...
[12]  Add -mxgot option to mips backend

Attachment: binutils-gnuxhash.patch
Description: binutils-gnuxhash.patch

Attachment: glibc-gnuxhash.patch
Description: glibc-gnuxhash.patch

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]