[ELF] Provide the GNU hash function in libObject

[jhuber6]

Summary

GNU uses a different hashing function compared to the sys-V standard
function already provided in libObject. This is already used internally
in LLD for generating synthetic sections. This patch simply extracts
this definition and makes it availible to other users of libObject.
This is done in preparation for supporting symbol name lookups via the
GNU hash table.

[MaskRay]

This patch may not be needed. You can add it as part of the patch using hashGnu. The duplicate in lld/ELF does not matter. When the openmp patches are proven to be mature, we can consider removing duplicate code in lld/ELF.

[jhuber6]

In D132696#3750807, @MaskRay wrote:

This patch may not be needed. You can add it as part of the patch using hashGnu. The duplicate in lld/ELF does not matter. When the openmp patches are proven to be mature, we can consider removing duplicate code in lld/ELF.

I was planning on adding GNU_HASH support on top of the HASH support in the other patch and figured this was an easy part to factor out. I'm not sure what you mean by the OpenMP patches being mature, are you talking about abandoning D131309 and just doing it directly inside of the OpenMP runtime and then merging it back into Elf.h some other time?

[jhenderson]

LGTM, but don't land this without the other patches in the stack being accepted.

I'm not sure I understand @MaskRay's objection to removing it from LLD at the same time. There doesn't seem to be any benefit from having the code in two places, given that it's not made the rest of the LLD code more complex.

lld/ELF/SyntheticSections.cpp

for (auto i = symbols.begin(), e = symbols.end(); i != e; ++i) {
     // Write a hash bucket. Hash buckets contain indices in the following hash
     // value table.
     write32(buckets + i->bucketIdx,
             getPartition().dynSymTab->getSymbolIndex(i->sym));
     oldBucket = i->bucketIdx;
   }
 }
 
-static uint32_t hashGnu(StringRef name) {
-  uint32_t h = 5381;
-  for (uint8_t c : name)
-    h = (h << 5) + h + c;
-  return h;
-}
-
 // Add symbols to this symbol hash table. Note that this function
 // destructively sort a given vector -- which is needed because
 // GNU-style hash table places some sorting requirements.
 void GnuHashTableSection::addSymbols(SmallVectorImpl<SymbolTableEntry> &v) {
   // We cannot use 'auto' for Mid because GCC 6.1 cannot deduce
   // its type correctly.
   auto mid =
       std::stable_partition(v.begin(), v.end(), [&](const SymbolTableEntry &s) {

llvm/include/llvm/Object/ELF.h

for (char C : SymbolName) {
     g = h & 0xf0000000L;
     if (g != 0)
       h ^= g >> 24;
     h &= ~g;
   }
   return h;
 }
 
+/// This function returns the hash value for a symbol in the .dynsym section
+/// for the GNU hash table. The implementation is defined in the GNU hash ABI.
+/// REF : https://sourceware.org/git/?p=binutils-gdb.git;a=blob;f=bfd/elf.c#l222
+inline uint32_t hashGnu(StringRef Name) {
+  uint32_t H = 5381;
+  for (uint8_t C : Name)
+    H = (H << 5) + H + C;
+  return H;
+}
+
 } // end namespace object
 } // end namespace llvm
 
 #endif // LLVM_OBJECT_ELF_H