Fix sysvhash function

[urnathan]

Summary

I had reason to look at hashSysV, the dynlib hash function. It's a rather awkward formulation -- taken almost straight from the SysV docs. But I noticed it is implemented incorrectly. Specifically it treats the symbol name as a set of plain chars, rather than unsigned chars, as the documented SysV hash treats them. For traditional names formed from a subset of 7-bit ASCII that's not a material difference. But for host ABIs with plain char signed (like x86), this will fail for high-bit chars. And we're in unicode UTF8 world now.[*]

So, use uint8_t, as the hashGnu function does.

Now, the loop is hard to optimize, and this reformulation removes 6 insns from the 16 insn loop on x86. There are 3 changes (all of which are too hard for clang and gcc to spot right now)

1. the 'if (g)' test is meaningless. We're xoring with g, so if it's zero, that's a nop anyway. As it happens, on x86 we compute the xor anyway and then cmov it. So, just drop it.

2. the ending 'h ^= g' clears the top 4 bits. But those 4 bits will get shifted out at the start of the next iteration. We can remove sink this mask out of the loop.

3. the final change is to mask wth 0xf0 after shifting by 24 bits, rather than before by 0xf0<<24, as that increases the likelihood of the ISA being able to use a short immediate mask operand. That's not the case for x86, but plenty of risc ISAs would need to materialize the larger constant somewhere.

I've added unit tests, and verified the hash values against binutil's implementation.

• Elf itself does not talk about character sets for symbol names -- they're merely NUL-terminated sequences of bytes.

FYI the refactoring will shortly be applied to binutils

[MaskRay]

Elf itself does not talk about character sets for symbol names -- they're merely NUL-terminated sequences of bytes.

Elf => ELF

---

Thanks for the patch! The generic ABI code fragment may have an oversight.
When long represents a 64-bit integer, elf_hash((const unsigned char *)"\xff\x0f\x0f\x0f\x0f\x0f\x12") returns 0x100000002, larger than UINT32_MAX.
I created a post on https://groups.google.com/g/generic-abi/c/8J_jtjsonrE

llvm/include/llvm/Object/ELF.h

1245

return H & 0x0fffffff;

llvm/unittests/Object/ELFTest.cpp

275

utf8 => UTF-8

[jhenderson]

Please remember to upload your patches with full context.

I'll leave @MaskRay to do the review of the logic, based on his discussion on the gABI list.

llvm/unittests/Object/ELFTest.cpp

275

Comments should end in a trailing "."

277–278

I'm not sure what this comment is trying to say. What do you mean by "feedback"? Could you reword it a bit, please?

[MaskRay]

llvm/unittests/Object/ELFTest.cpp

289

Here is a nice test case (all alphanumeric characters!) to trigger an overflow issue for the generic ABI function. elf_hash((const unsigned char *)"ZZZZZW9p")) == 100000000 (https://maskray.me/blog/2023-04-12-elf-hash-function)

[urnathan]

In D147890#4260002, @MaskRay wrote:

Thanks for the patch! The generic ABI code fragment may have an oversight.
When long represents a 64-bit integer, elf_hash((const unsigned char *)"\xff\x0f\x0f\x0f\x0f\x0f\x12") returns 0x100000002, larger than UINT32_MAX.

Yeah, I noticed that too, but the original algorithm was when long was always 32 bits and uint32_t and friends either didn't exist or were very rare. (can't respond to the gabi link you provided).

Anyway, adding your testcase.

llvm/include/llvm/Object/ELF.h

return createError("a section " + getSecIndexForError(*this, Section) +
                        "section name string table");
   return StringRef(DotShstrtab.data() + Offset);
 }
 
 /// This function returns the hash value for a symbol in the .dynsym section
 /// Name of the API remains consistent as specified in the libelf
 /// REF : http://www.sco.com/developers/gabi/latest/ch5.dynamic.html#hash
 inline unsigned hashSysV(StringRef SymbolName) {
-  unsigned h = 0, g;
-  for (char C : SymbolName) {
-    h = (h << 4) + C;
-    g = h & 0xf0000000L;
-    if (g != 0)
-      h ^= g >> 24;
-    h &= ~g;
+  uint32_t H = 0;
+  for (uint8_t C : SymbolName) {
+    H = (H << 4) + C;
+    H ^= (H >> 24) & 0xf0;
   }
-  return h;
+  return H & 0xfffffff;
 }
 
 /// 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

llvm/unittests/Object/ELFTest.cpp

TEST(ELFTest, DataRegionTest) {
   // data end pointers.
   Region = {Data.data(), Data.data() + Data.size()};
 
   CheckOperator(Region);
   const char *ErrMsg2 = "can't read past the end of the file";
   EXPECT_THAT_ERROR(Region[3].takeError(), FailedWithMessage(ErrMsg2));
   EXPECT_THAT_ERROR(Region[4].takeError(), FailedWithMessage(ErrMsg2));
 }
+
+// Test the sysV and the gnu hash functions, particularly with utf8 unicode
+TEST(ELFTest, Hash) {
+  // Symbols long enough to have feedback
+  EXPECT_EQ(hashSysV("FooBarBazToto"), 0x5ec3e8fU);
+  EXPECT_EQ(hashGnu("FooBarBazToto"), 0x5478be61U);
+  EXPECT_EQ(hashSysV(u8"boom💥pants"), 0x5a0cf53U);
+  EXPECT_EQ(hashGnu(u8"boom💥pants"), 0xf5dda2deU);
+  EXPECT_EQ(hashSysV(u8"woot!🧙 💑 🌈"), 0x3522e38U);
+  EXPECT_EQ(hashGnu(u8"woot!🧙 💑 🌈"), 0xf7603f3U);
+}