[ELF] A shared object is needed if any of its occurrences is needed

[MaskRay]

Summary

If a DSO appears more than once with and without --as-needed, ld.bfd and gold consider --no-as-needed to takes precedence over --as-needed. lld didn't and this patch makes it do so.

This makes it a bit away from the position-dependent behavior (how
different occurrences of the same DSO interact) and protects us from
some mysterious runtime errors: if some interceptor libraries add their
own --no-as-needed dependencies (e.g. librt.so), and the user
application specifies -Wl,--as-needed -lrt , the absence of the
DT_NEEDED entry would make dlsym(RTLD_NEXT, "clock_gettime") return NULL
and would break at runtime.

[ruiu]

This is a tricky case, and arguably the current behavior should be considered correct, although there's no definition of what's right and what's wrong. Could you share the background of this change so that I can understand why you want this?

ELF/SymbolTable.cpp

97 ↗

(On Diff #179520)

Please replace auto with the actual type.

[MaskRay]

The test case suggests its usage: ld.lld %t.o %tb.so --as-needed %ta.so --no-as-needed %ta.so -o %t

The behavior I observed: both ld.bfd and gold consider a DSO needed if any occurrence of it is not wrapped by --as-needed. However, lld doesn't do so: we uniquify DSOs by their SONAME, and may drop a DT_NEEDED entry if the first occurrence is wrapped by --as-needed.

This patch makes it consistent with ld.bfd/gold in this aspect and moves a bit away from the not-so-good position-dependent behavior.
(An as-needed DSO resembles an archive file to some extent. I understand it is difficult to make it consistent with ld.bfd/gold in every case (gold diverges from ld.bfd in some aspects). But this behavior is what I think reasonable)

ELF/SymbolTable.cpp

97 ↗

(On Diff #179520)

The actual type of R is very long std::pair<llvm::DenseMapIterator<llvm::StringRef, lld::elf::InputFile *, llvm::DenseMapInfo<llvm::StringRef>, llvm::detail::DenseMapPair<llvm::StringRef, lld::elf::InputFile *>, false>, bool>

It is a pair consisting of an iterator to the element, and a bool denoting whether the insertion took place (the same as https://en.cppreference.com/w/cpp/container/map/emplace).

[ruiu]

Although I understand how your change works, I don't understand why you need this in the first place. What is the use case in which you want to specify the same DSO more than once in the same command line, with and without --as-needed?

[MaskRay]

In D56089#1341040, @ruiu wrote:

Although I understand how your change works, I don't understand why you need this in the first place. What is the use case in which you want to specify the same DSO more than once in the same command line, with and without --as-needed?

The AsNeeded status of a.so can also come from the linker script command AS_NEEDED. If an executable links in the script b.so (AS_NEEDED(a.so)), but really wants a.so to be loaded, it may link in a.so explicitly. Without the patch (making it consistent with ld.bfd/gold), the DT_NEEDED entry of a.so will be dropped.

Now the question is why we want to ensure some DSOs in DT_NEEDED entries. It can be related to static constructors and DSO loading order problems (honestly I think many of them are just user error...).

[ruiu]

What program are you actually trying to fix? Honestly I feel no one should depends on such a corner case behavior of GNU linkers.

[MaskRay]

https://bugs.llvm.org/show_bug.cgi?id=15823#c0 (clang -fuse-ld=lld -fsanitize=address test.c -Wl,--as-needed -ldl -lrt) is one real world case.

That example does not work today because libclang_rt.asan-x86_64.a has other references (shm_open) to librt.so so librt.so is needed.

But the idea may apply on other interceptor libraries: they may have their own --no-as-needed dependencies (librt.so), if the user application specifies -Wl,--as-needed -lrt , it will break (dlsym(RTLD_NEXT, "clock_gettime")) at runtime.

[ruiu]

I'm still a bit hesitant about doing this, but perhaps it is better to accept this because without this a mysterious runtime error could happen as you explained. But I wonder if you can simplify it even more. Can you do something like this? I didn't test this but I think we don't need a hash table.

https://gist.github.com/rui314/92fdae6c0678528e76ad1a5e8818a57f

[MaskRay]

Add some comments

[MaskRay]

In D56089#1341366, @ruiu wrote:

I'm still a bit hesitant about doing this, but perhaps it is better to accept this because without this a mysterious runtime error could happen as you explained. But I wonder if you can simplify it even more. Can you do something like this? I didn't test this but I think we don't need a hash table.

https://gist.github.com/rui314/92fdae6c0678528e76ad1a5e8818a57f

Thank you for considering this. The actual code addition is one line (minus comments and newline), the benefit is the fix of some potential mysterious runtime errors. In addition, it fixes one position-dependent behavior. There are two introduced by --as-needed

• --as-needed influences DSOs coming after it. This is inherent and unfixable
• How the multiple occurrences of the same DSO interact. It was position-dependent and now independent.

I've read your gist, but I think the quadratic behavior may be undesired. The number of DT_NEEDED entries is usually small (100), but some of our internal executables can have thousands of dependencies. By keeping the hash table as is, the increase of memory usage is small but the performance improvement is large.

[ruiu]

Quadratic behavior should be fine as a square of a few thousand is still small. We don't need to worry too much about it. That said, if you don't like it, it is also fine as long as the code is as easy to understand as the more dumb-but-simple code. I'd think that the current comment is not suffice because it only explains what that code does. Please copy my comment which explains why we want it.

Also please avoid try_emplace as the code looks a bit too smart. The actual values of R.first->second and R->second are not obvious. I'd write something like this.

F->parseSoName();
if (errorCount())
  return;

// DSO are uniquified by soname.
InputFile *&Existing = SoNames[F->SoName];
if (Existing) {
  if (F->IsNeeded)
    cast<SharedFile<ELFT>>(Existing)->IsNeeded = true;
  return;
}
Existing = F;

[MaskRay]

Spell out the two components of the try_emplace return value

[MaskRay]

In D56089#1341384, @ruiu wrote:

Quadratic behavior should be fine as a square of a few thousand is still small. We don't need to worry too much about it. That said, if you don't like it, it is also fine as long as the code is as easy to understand as the more dumb-but-simple code. I'd think that the current comment is not suffice because it only explains what that code does. Please copy my comment which explains why we want it.

Also please avoid try_emplace as the code looks a bit too smart. The actual values of R.first->second and R->second are not obvious. I'd write something like this.

F->parseSoName();
if (errorCount())
  return;

// DSO are uniquified by soname.
InputFile *&Existing = SoNames[F->SoName];
if (Existing) {
  if (F->IsNeeded)
    cast<SharedFile<ELFT>>(Existing)->IsNeeded = true;
  return;
}
Existing = F;

DenseMap::try_emplace is a C++17 flavored function name that powers insert, which has been used in 30+ llvm files and 20+ clang files. I know lld uses a slightly different style, so I have spelled out the two components. WasInserted is picked according to the existing name convention in another place of lld.

[ruiu]

LGTM

ELF/SymbolTable.cpp

100 ↗

(On Diff #179568)

I still prefer to add

if (errorCount())
  return;

here because there's no reason to group WasInserted and errorCount() in terms of semantics.

[MaskRay]

Check `if (errorCount) early

lld/trunk/ELF/SymbolTable.h

private:
   std::vector<Symbol *> SymVector;
 
   // Comdat groups define "link once" sections. If two comdat groups have the
   // same name, only one of them is linked, and the other is ignored. This set
   // is used to uniquify them.
   llvm::DenseSet<llvm::CachedHashStringRef> ComdatGroups;
 
   // Set of .so files to not link the same shared object file more than once.
-  llvm::DenseSet<StringRef> SoNames;
+  llvm::DenseMap<StringRef, InputFile *> SoNames;
 
   // A map from demangled symbol names to their symbol objects.
   // This mapping is 1:N because two symbols with different versions
   // can have the same name. We use this map to handle "extern C++ {}"
   // directive in version scripts.
   llvm::Optional<llvm::StringMap<std::vector<Symbol *>>> DemangledSyms;
 
   // For LTO.
   std::unique_ptr<BitcodeCompiler> LTO;
 };
 
 extern SymbolTable *Symtab;
 } // namespace elf
 } // namespace lld
 
 #endif

lld/trunk/ELF/SymbolTable.cpp

template <class ELFT> void SymbolTable::addFile(InputFile *File) {
 
   if (Config->Trace)
     message(toString(File));
 
   // .so file
   if (auto *F = dyn_cast<SharedFile<ELFT>>(File)) {
     // DSOs are uniquified not by filename but by soname.
     F->parseSoName();
-    if (errorCount() || !SoNames.insert(F->SoName).second)
+    if (errorCount())
       return;
+
+    // If a DSO appears more than once on the command line with and without
+    // --as-needed, --no-as-needed takes precedence over --as-needed because a
+    // user can add an extra DSO with --no-as-needed to force it to be added to
+    // the dependency list.
+    DenseMap<StringRef, InputFile *>::iterator It;
+    bool WasInserted;
+    std::tie(It, WasInserted) = SoNames.try_emplace(F->SoName, F);
+    cast<SharedFile<ELFT>>(It->second)->IsNeeded |= F->IsNeeded;
+    if (!WasInserted)
+      return;
+
     SharedFiles.push_back(F);
     F->parseRest();
     return;
   }
 
   // LLVM bitcode file
   if (auto *F = dyn_cast<BitcodeFile>(File)) {
     BitcodeFiles.push_back(F);

lld/trunk/test/ELF/as-needed-not-in-regular.s

 
 # RUN: ld.lld %t.o %tb.so --as-needed %ta.so --gc-sections -o %t
 # RUN: llvm-readelf -d %t | FileCheck %s
 
 # The symbol a1 (defined in a.so) is not referenced by a regular object,
 # the reference to a2 is weak, don't add a DT_NEEDED entry for a.so.
 # CHECK-NOT: a.so
 
+# RUN: ld.lld %t.o %tb.so --as-needed %ta.so --no-as-needed %ta.so -o %t
+# RUN: llvm-readelf -d %t | FileCheck %s -check-prefix=NEEDED
+
+# a.so is needed because one of its occurrences is needed.
+# NEEDED: a.so
+
 .global _start
 .weak a2
 _start:
   jmp b@PLT
   jmp a2