[ThinLTO] Avoid archive member collisions

[davide]

Summary

https://llvm.org/bugs/show_bug.cgi?id=30665
See the comment in the code && the PR for a detailed description.

[pcc]

It seems that this does not entirely solve the problem -- you will still have collisions if two files happen to have the same size.

The gold plugin solves this problem by incorporating the byte offset within the archive file into the filename it passes to the LTO library. Would it be possible to do something similar here?

[mehdi_amini]

In D25495#567829, @pcc wrote:

It seems that this does not entirely solve the problem -- you will still have collisions if two files happen to have the same size.

The gold plugin solves this problem by incorporating the byte offset within the archive file into the filename it passes to the LTO library. Would it be possible to do something similar here?

Will it solve the problem?
If you have two archives with the same size, and the two member with the same name are the first one in the archive, they'll likely start at the same offset, wouldn't you get a collision again?

[pcc]

This patch is already including the archive name as part of the filename, which would seem to be enough to avoid a collision in that case.

[mehdi_amini]

Oh sure, as long as the full path to the archive is kept and not only the archive name itself, that should be fine!

ELF/InputFiles.cpp

718 ↗

(On Diff #74318)

s/size of the archive/size of the member buffer/

[davide]

Thanks for clarifying, Peter. Here's a new version of the patch. I decided to store the information about the offset in the archive in class InputFile as we do for the archive name already.

[ruiu]

ELF/InputFiles.cpp

726–727 ↗

(On Diff #74393)

Can you use the object address as a unique identifier instead? I mean utostr((uint64_t)&MB) is always unique.

[davide]

ELF/InputFiles.cpp

726–727 ↗

(On Diff #74393)

Maybe, but I'd like to double check with Peter to make sure it's fine on lib/LTO side (probably it is).

[pcc]

ELF/InputFiles.cpp

726–727 ↗

(On Diff #74393)

I'd prefer not to do that, for a couple of reasons:

1. these names are used by lib/LTO to form file names for save-temps, and it's probably best if that remains deterministic
2. eventually I think we will need to plumb the file name and offset into lib/LTO so that ThinLTO can use it to reload the input file in another process.

[davide]

OK, makes sense. Are you fine with the rest of the patch?

[mehdi_amini]

ELF/InputFiles.cpp

726–727 ↗

(On Diff #74393)

For 2), that would tie us to a "file based" API, I'll look closely at the benefit before going this route.

[ruiu]

If we put aside (2) for now, all the plumbing of OffsetInArchive is just to create a unique filename, which I think I don't like. There are other ways to generate a deterministic unique filename. For example, you could add static int Counter = 0 to BitcodeFile and use the counter value as part of a filename (and increment it every time you use it).

[ruiu]

Isn't ArchiveName a full path? If you concatenate a full path archive name and a filename inside of the archive, does it become a unique identifier?

[davide]

In D25495#568482, @ruiu wrote:

If we put aside (2) for now, all the plumbing of OffsetInArchive is just to create a unique filename, which I think I don't like. There are other ways to generate a deterministic unique filename. For example, you could add static int Counter = 0 to BitcodeFile and use the counter value as part of a filename (and increment it every time you use it).

I'm not sure I like exposing a global with static lifetime to avoid threading informations properly into the linker. If it would be a awful lot of work, I'd agree with you, but it seems it's not.

[davide]

In D25495#568483, @ruiu wrote:

Isn't ArchiveName a full path? If you concatenate a full path archive name and a filename inside of the archive, does it become a unique identifier?

No, it does not, because you can have a valid archive which contains two member functions with the same name.

[davide]

In D25495#568483, @ruiu wrote:

Isn't ArchiveName a full path? If you concatenate a full path archive name and a filename inside of the archive, does it become a unique identifier?

No, it does not, because you can have a valid archive which contains two member functions with the same name.

[ruiu]

That's true. That means when we print out an error message, we have the same problem that users can't identify which file is wrong. I'm wondering if InputFile::getName() should return a unique name, such as "some/path/foobar.a:123:x.o" where 123 is an offset in the archive.

[pcc]

In D25495#568493, @ruiu wrote:

I'm wondering if InputFile::getName() should return a unique name, such as "some/path/foobar.a:123:x.o" where 123 is an offset in the archive.

That might be something we could do in lld::elf::getFilename(). It could be confusing in the normal case, so maybe we could do it only if the archive contains duplicate names?

ELF/InputFiles.cpp

491 ↗

(On Diff #74411)

If this is a thin archive, I don't think getChildOffset will give us the right value (looking at the implementation, it appears that it will return a garbage value for thin archive members). Maybe return 0 if thin?

[davide]

In D25495#568522, @pcc wrote:

In D25495#568493, @ruiu wrote:

I'm wondering if InputFile::getName() should return a unique name, such as "some/path/foobar.a:123:x.o" where 123 is an offset in the archive.

That might be something we could do in lld::elf::getFilename(). It could be confusing in the normal case, so maybe we could do it only if the archive contains duplicate names?

Maybe, but I still think the change belongs to a different patch

ELF/InputFiles.cpp

491 ↗

(On Diff #74411)

Oh yeah, good catch.

[pcc]

In D25495#568532, @davide wrote:

In D25495#568522, @pcc wrote:

In D25495#568493, @ruiu wrote:

I'm wondering if InputFile::getName() should return a unique name, such as "some/path/foobar.a:123:x.o" where 123 is an offset in the archive.

That might be something we could do in lld::elf::getFilename(). It could be confusing in the normal case, so maybe we could do it only if the archive contains duplicate names?

Maybe, but I still think the change belongs to a different patch

Agreed. Rui, what do you think?

This LGTM as far as I'm concerned though.

[ruiu]

I will try to see how my proposal work but it doesn't have to block this. LGTM.

[ruiu]

Does this work for --whole-archive?

lld/trunk/ELF/InputFiles.h

public:
   StringRef getName() const { return MB.getBufferIdentifier(); }
   MemoryBufferRef MB;
 
   // Filename of .a which contained this file. If this file was
   // not in an archive file, it is the empty string. We use this
   // string for creating error messages.
   StringRef ArchiveName;
 
+  // If this file is in an archive, the member contains the offset of
+  // the file in the archive. Otherwise, it's just zero. We store this
+  // field so that we can pass it to lib/LTO in order to disambiguate
+  // between objects.
+  uint64_t OffsetInArchive;
+
   // If this is an architecture-specific file, the following members
   // have ELF type (i.e. ELF{32,64}{LE,BE}) and target machine type.
   ELFKind EKind = ELFNoneKind;
   uint16_t EMachine = llvm::ELF::EM_NONE;
 
   static void freePool();
 
 protected:

 
 // An ArchiveFile object represents a .a file.
 class ArchiveFile : public InputFile {
 public:
   explicit ArchiveFile(MemoryBufferRef M) : InputFile(ArchiveKind, M) {}
   static bool classof(const InputFile *F) { return F->kind() == ArchiveKind; }
   template <class ELFT> void parse();
 
-  // Returns a memory buffer for a given symbol. An empty memory buffer
+  // Returns a memory buffer for a given symbol and the offset in the archive
+  // for the member. An empty memory buffer and an offset of zero
   // is returned if we have already returned the same memory buffer.
   // (So that we don't instantiate same members more than once.)
-  MemoryBufferRef getMember(const Archive::Symbol *Sym);
+  std::pair<MemoryBufferRef, uint64_t> getMember(const Archive::Symbol *Sym);
 
 private:
   std::unique_ptr<Archive> File;
   llvm::DenseSet<uint64_t> Seen;
 };
 
 class BitcodeFile : public InputFile {
 public:
public:
   static bool classof(const InputFile *F) { return F->kind() == BinaryKind; }
 
   template <class ELFT> InputFile *createELF();
 
 private:
   std::vector<uint8_t> ELFData;
 };
 
-InputFile *createObjectFile(MemoryBufferRef MB, StringRef ArchiveName = "");
+InputFile *createObjectFile(MemoryBufferRef MB, StringRef ArchiveName = "",
+                            uint64_t OffsetInArchive = 0);
 InputFile *createSharedFile(MemoryBufferRef MB);
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/trunk/ELF/InputFiles.cpp

template <class ELFT> void ArchiveFile::parse() {
   File = check(Archive::create(MB), "failed to parse archive");
 
   // Read the symbol table to construct Lazy objects.
   for (const Archive::Symbol &Sym : File->symbols())
     Symtab<ELFT>::X->addLazyArchive(this, Sym);
 }
 
 // Returns a buffer pointing to a member file containing a given symbol.
-MemoryBufferRef ArchiveFile::getMember(const Archive::Symbol *Sym) {
+std::pair<MemoryBufferRef, uint64_t>
+ArchiveFile::getMember(const Archive::Symbol *Sym) {
   Archive::Child C =
       check(Sym->getMember(),
             "could not get the member for symbol " + Sym->getName());
 
   if (!Seen.insert(C.getChildOffset()).second)
-    return MemoryBufferRef();
+    return {MemoryBufferRef(), 0};
 
   MemoryBufferRef Ret =
       check(C.getMemoryBufferRef(),
             "could not get the buffer for the member defining symbol " +
                 Sym->getName());
 
   if (C.getParent()->isThin() && Driver->Cpio)
     Driver->Cpio->append(relativeToRoot(check(C.getFullName())),
                          Ret.getBuffer());
-
-  return Ret;
+  if (C.getParent()->isThin())
+    return {Ret, 0};
+  return {Ret, C.getChildOffset()};
 }
 
 template <class ELFT>
 SharedFile<ELFT>::SharedFile(MemoryBufferRef M)
     : ELFFileBase<ELFT>(Base::SharedKind, M), AsNeeded(Config->AsNeeded) {}
 
 template <class ELFT>
 const typename ELFT::Shdr *
return Symtab<ELFT>::X->addCommon(NameRef, ObjSym.getCommonSize(),
                                       Visibility, STT_OBJECT, F);
 
   return Symtab<ELFT>::X->addBitcode(NameRef, Binding, Visibility, Type,
                                      CanOmitFromDynSym, F);
 }
 
 template <class ELFT>
 void BitcodeFile::parse(DenseSet<StringRef> &ComdatGroups) {
-  Obj = check(lto::InputFile::create(MB));
+
+  // Here we pass a new MemoryBufferRef which is identified by ArchiveName
+  // (the fully resolved path of the archive) + member name + offset of the
+  // member in the archive.
+  // ThinLTO uses the MemoryBufferRef identifier to access its internal
+  // data structures and if two archives define two members with the same name,
+  // this causes a collision which result in only one of the objects being
+  // taken into consideration at LTO time (which very likely causes undefined
+  // symbols later in the link stage).
+  Obj = check(lto::InputFile::create(MemoryBufferRef(
+      MB.getBuffer(), Saver.save(ArchiveName + MB.getBufferIdentifier() +
+                                 utostr(OffsetInArchive)))));
   DenseSet<const Comdat *> KeptComdats;
   for (const auto &P : Obj->getComdatSymbolTable()) {
     StringRef N = Saver.save(P.first());
     if (ComdatGroups.insert(N).second)
       KeptComdats.insert(&P.second);
   }
 
   for (const lto::InputFile::Symbol &ObjSym : Obj->symbols())
return createELFFile<ObjectFile>(MemoryBufferRef(
       StringRef((char *)ELFData.data(), Size), MB.getBufferIdentifier()));
 }
 
 static bool isBitcode(MemoryBufferRef MB) {
   using namespace sys::fs;
   return identify_magic(MB.getBuffer()) == file_magic::bitcode;
 }
 
-InputFile *elf::createObjectFile(MemoryBufferRef MB, StringRef ArchiveName) {
+InputFile *elf::createObjectFile(MemoryBufferRef MB, StringRef ArchiveName,
+                                 uint64_t OffsetInArchive) {
   InputFile *F =
       isBitcode(MB) ? new BitcodeFile(MB) : createELFFile<ObjectFile>(MB);
   F->ArchiveName = ArchiveName;
+  F->OffsetInArchive = OffsetInArchive;
   return F;
 }
 
 InputFile *elf::createSharedFile(MemoryBufferRef MB) {
   return createELFFile<SharedFile>(MB);
 }
 
 MemoryBufferRef LazyObjectFile::getBuffer() {

lld/trunk/ELF/SymbolTable.cpp

void SymbolTable<ELFT>::addLazyArchive(ArchiveFile *F,
   // undefined symbol never shows up, this lazy symbol will get to the end of
   // the link and must be treated as the weak undefined one. We already marked
   // this symbol as used when we added it to the symbol table, but we also need
   // to preserve its type. FIXME: Move the Type field to Symbol.
   if (S->isWeak()) {
     replaceBody<LazyArchive>(S, *F, Sym, S->body()->Type);
     return;
   }
-  MemoryBufferRef MBRef = F->getMember(&Sym);
-  if (!MBRef.getBuffer().empty())
-    addFile(createObjectFile(MBRef, F->getName()));
+  std::pair<MemoryBufferRef, uint64_t> MBInfo = F->getMember(&Sym);
+  if (!MBInfo.first.getBuffer().empty())
+    addFile(createObjectFile(MBInfo.first, F->getName(), MBInfo.second));
 }
 
 template <class ELFT>
 void SymbolTable<ELFT>::addLazyObject(StringRef Name, LazyObjectFile &Obj) {
   Symbol *S;
   bool WasInserted;
   std::tie(S, WasInserted) = insert(Name);
   if (WasInserted) {

lld/trunk/ELF/Symbols.cpp

 }
 
 LazyObject::LazyObject(StringRef Name, LazyObjectFile &File, uint8_t Type)
     : Lazy(LazyObjectKind, Name, Type) {
   this->File = &File;
 }
 
 InputFile *LazyArchive::fetch() {
-  MemoryBufferRef MBRef = file()->getMember(&Sym);
+  std::pair<MemoryBufferRef, uint64_t> MBInfo = file()->getMember(&Sym);
 
   // getMember returns an empty buffer if the member was already
   // read from the library.
-  if (MBRef.getBuffer().empty())
+  if (MBInfo.first.getBuffer().empty())
     return nullptr;
-  return createObjectFile(MBRef, file()->getName());
+  return createObjectFile(MBInfo.first, file()->getName(), MBInfo.second);
 }
 
 InputFile *LazyObject::fetch() {
   MemoryBufferRef MBRef = file()->getBuffer();
   if (MBRef.getBuffer().empty())
     return nullptr;
   return createObjectFile(MBRef);
 }

lld/trunk/test/ELF/lto/Inputs/thin1.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-scei-ps4"
+
+define i32 @foo(i32 %goo) {
+entry:
+  %goo.addr = alloca i32, align 4
+  store i32 %goo, i32* %goo.addr, align 4
+  %0 = load i32, i32* %goo.addr, align 4
+  %1 = load i32, i32* %goo.addr, align 4
+  %mul = mul nsw i32 %0, %1
+  ret i32 %mul
+}

lld/trunk/test/ELF/lto/Inputs/thin2.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-scei-ps4"
+
+define i32 @blah(i32 %meh) #0 {
+entry:
+  %meh.addr = alloca i32, align 4
+  store i32 %meh, i32* %meh.addr, align 4
+  %0 = load i32, i32* %meh.addr, align 4
+  %sub = sub nsw i32 %0, 48
+  ret i32 %sub
+}

lld/trunk/test/ELF/lto/thin-archivecollision.ll

+; RUN: opt -module-summary %s -o %t.o
+; RUN: opt -module-summary %p/Inputs/thin1.ll -o %t.coll.o
+; RUN: llvm-ar rcs %t1.a %t.coll.o
+; RUN: opt -module-summary %p/Inputs/thin2.ll -o %t.coll.o
+; RUN: llvm-ar rcsc %t2.a %t.coll.o
+
+; RUN: ld.lld %t.o %t1.a %t2.a -o %t
+; RUN: llvm-nm %t | FileCheck %s
+
+; CHECK: T _start
+; CHECK: T blah
+; CHECK: T foo
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-scei-ps4"
+
+define i32 @_start() {
+entry:
+  %call = call i32 @foo(i32 23)
+  %call1 = call i32 @blah(i32 37)
+  ret i32 0
+}
+
+declare i32 @foo(i32) #1
+declare i32 @blah(i32) #1