[ELF] - Never create .gnu_hash with NBuckets == 0.

[grimar]

Summary

I suggest setting NBuckets so that it is always >= 0.

Currently, we can end up with NBuckets==0 and android loader
does not like it (see PR36537).

The gold linker as we know use predefined table with values for NBuckets
and it never produces output where NBuckets == 0.

In theory, we could drop the whole hash table in this case probably,
as the only use case I can imagine now where it might harm is when
binary contains only undefined symbols, so that without hash section,
the loader will have to lookup for some symbol instead of instantly getting
the info that there are no symbols from the empty hash table. It's unrealistic I think.

But I also think that we probably can go with a minimal amount of changes here for simplicity
and be consistent with gold and so just always use >= 1 value for NBuckets.

[peter.smith]

I think that this is the simplest change that will pass through Bionic loaders check. The other possibility I thought of which might be a bit more honest is to add one of the symbols to the table even if it were a reference, that would minimise the risk of some other tool from complaining about hash table structure problems.

Unfortunately the bionic loader doesn't look like it will accept an executable without at least one of the ELF hash or GNU hash sections being present (and if present having nbuckets being non 0). I've got it on my list of things to do to raise a defect on the loader as a hash table should be an optimisation.

[• rafael]

George Rimar via Phabricator via llvm-commits
<[e-mail]> writes:

Index: ELF/SyntheticSections.cpp

• ELF/SyntheticSections.cpp

+++ ELF/SyntheticSections.cpp
@@ -1799,15 +1799,16 @@

    return SS->CopyRelSec == nullptr && !SS->NeedsPltAddr;
  return !S.Sym->isDefined();
});

• if (Mid == V.end())
• return;
  
  We chose load factor 4 for the on-disk hash table. For each hash collision, the dynamic linker will compare a uint32_t hash value. Since the integer comparison is quite fast, we believe we can make the load factor even larger. 4 is just a conservative choice. NBuckets = std::max<size_t>((V.end() - Mid) / 4, 1);

Please update the comment to say:

• Why we want to keep this section: It indicates to a loader that the file exports no symbols.
• Why we can't use 0: The android loader doesn't support that.

With that, LGTM.

Thanks,
Rafael

[ruiu]

ELF/SyntheticSections.cpp

1805

Please separate sentences with blank lines. The sentence about an Android loader workaround and "We chose ..." are talking about completely different stuff, so this is confusing.

ELF/SyntheticSections.cpp

void GnuHashTableSection::addSymbols(std::vector<SymbolTableEntry> &V) {
   std::vector<SymbolTableEntry>::iterator Mid =
       std::stable_partition(V.begin(), V.end(), [](const SymbolTableEntry &S) {
         // Shared symbols that this executable preempts are special. The dynamic
         // linker has to look them up, so they have to be in the hash table.
         if (auto *SS = dyn_cast<SharedSymbol>(S.Sym))
           return SS->CopyRelSec == nullptr && !SS->NeedsPltAddr;
         return !S.Sym->isDefined();
       });
-  if (Mid == V.end())
-    return;
 
-  // We chose load factor 4 for the on-disk hash table. For each hash
-  // collision, the dynamic linker will compare a uint32_t hash value.
-  // Since the integer comparison is quite fast, we believe we can make
-  // the load factor even larger. 4 is just a conservative choice.
+  // Even if the hash table does not contain symbols, we still want to keep the
+  // section to indicate to a loader that the file exports no symbols. We can't
+  // have zero buckets because the android loader doesn't support that. We chose
+  // load factor 4 for the on-disk hash table. For each hash collision, the
+  // dynamic linker will compare a uint32_t hash value. Since the integer
+  // comparison is quite fast, we believe we can make the load factor even
+  // larger. 4 is just a conservative choice.
   NBuckets = std::max<size_t>((V.end() - Mid) / 4, 1);
 
+  if (Mid == V.end())
+    return;
+
   for (SymbolTableEntry &Ent : llvm::make_range(Mid, V.end())) {
     Symbol *B = Ent.Sym;
     uint32_t Hash = hashGnu(B->getName());
     uint32_t BucketIdx = Hash % NBuckets;
     Symbols.push_back({B, Ent.StrTabOffset, Hash, BucketIdx});
   }
 
   std::stable_sort(

test/ELF/arm-execute-only.s

 // REQUIRES: arm
 
 // RUN: llvm-mc -filetype=obj -triple=armv7-pc-linux %s -o %t.o
 // RUN: ld.lld %t.o -o %t.so -shared
 // RUN: llvm-readelf -l %t.so | FileCheck %s
 
 // RUN: ld.lld %t.o %t.o -o %t.so -shared
 // RUN: llvm-readelf -l %t.so | FileCheck %s
 
 // RUN: echo ".section .foo,\"ax\"; \
 // RUN:       bx lr" > %t.s
 // RUN: llvm-mc -filetype=obj -triple=armv7-pc-linux %t.s -o %t2.o
 // RUN: ld.lld %t.o %t2.o -o %t.so -shared
 // RUN: llvm-readelf -l %t.so | FileCheck --check-prefix=DIFF %s
 
 // CHECK-NOT:  LOAD
-// CHECK:      LOAD           0x000000 0x00000000 0x00000000 0x00169  0x00169  R   0x1000
+// CHECK:      LOAD           0x000000 0x00000000 0x00000000 0x0016d  0x0016d  R   0x1000
 // CHECK:      LOAD           0x001000 0x00001000 0x00001000 0x{{.*}} 0x{{.*}} R E 0x1000
 // CHECK:      LOAD           0x002000 0x00002000 0x00002000 0x{{.*}} 0x{{.*}}   E 0x1000
 // CHECK:      LOAD           0x003000 0x00003000 0x00003000 0x00038  0x00038  RW  0x1000
 // CHECK-NOT:  LOAD
 
 // CHECK: 01     .dynsym .gnu.hash .hash .dynstr
 // CHECK: 02     .text
 // CHECK: 03     .foo
 // CHECK: 04     .dynamic
 
 // DIFF-NOT:  LOAD
-// DIFF:      LOAD           0x000000 0x00000000 0x00000000 0x00149 0x00149 R   0x1000
+// DIFF:      LOAD           0x000000 0x00000000 0x00000000 0x0014d 0x0014d R   0x1000
 // DIFF:      LOAD           0x001000 0x00001000 0x00001000 0x0000c 0x0000c R E 0x1000
 // DIFF:      LOAD           0x002000 0x00002000 0x00002000 0x00038 0x00038 RW  0x1000
 // DIFF-NOT:  LOAD
 
 // DIFF: 01     .dynsym .gnu.hash .hash .dynstr
 // DIFF: 02     .text .foo
 // DIFF: 03     .dynamic
 
         bx lr
         .section .foo,"axy"
         bx lr

test/ELF/dynamic-no-rosegment.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
 # RUN: ld.lld -shared --no-rosegment -z rodynamic -o %t %t.o
 # RUN: llvm-readobj -dynamic-table -s %t | FileCheck %s
 
 # CHECK:      DynamicSection [ (7 entries)
 # CHECK-NEXT:   Tag                Type                 Name/Value
 # CHECK-NEXT:   0x0000000000000006 SYMTAB               0x120
 # CHECK-NEXT:   0x000000000000000B SYMENT               24 (bytes)
-# CHECK-NEXT:   0x0000000000000005 STRTAB               0x1D0
+# CHECK-NEXT:   0x0000000000000005 STRTAB               0x1D8
 # CHECK-NEXT:   0x000000000000000A STRSZ                1 (bytes)
 # CHECK-NEXT:   0x000000006FFFFEF5 GNU_HASH             0x138
-# CHECK-NEXT:   0x0000000000000004 HASH                 0x150
+# CHECK-NEXT:   0x0000000000000004 HASH                 0x154
 # CHECK-NEXT:   0x0000000000000000 NULL                 0x0
 # CHECK-NEXT: ]

test/ELF/gnu-hash-table.s

 # EMPTY-NEXT:     Size: 0
 # EMPTY-NEXT:     Binding: Global
 # EMPTY-NEXT:     Type: None
 # EMPTY-NEXT:     Other: 0
 # EMPTY-NEXT:     Section: Undefined
 # EMPTY-NEXT:   }
 # EMPTY-NEXT: ]
 # EMPTY:      GnuHashTable {
-# EMPTY-NEXT:   Num Buckets: 0
+# EMPTY-NEXT:   Num Buckets: 1
 # EMPTY-NEXT:   First Hashed Symbol Index: 2
 # EMPTY-NEXT:   Num Mask Words: 1
 # EMPTY-NEXT:   Shift Count: 5
 # EMPTY-NEXT:   Bloom Filter: [0x0]
-# EMPTY-NEXT:   Buckets: []
+# EMPTY-NEXT:   Buckets: [0]
 # EMPTY-NEXT:   Values: []
 # EMPTY-NEXT: }
 
 # I386:      Format: ELF32-i386
 # I386:      Arch: i386
 # I386:      AddressSize: 32bit
 # I386:      Sections [
 # I386:          Name: .gnu.hash