Fix Wasm symbol name collisions

[ncw]

Summary

If you link in two object files with duplicate local symbol names, the link should succeed - but the "names" section is populated with duplicate names. According to binaryen, this is invalid and wasm-dis will fail.

When linking ELF files, the symbol names are "budged" to avoid the collision in the final symbol table.

I've added budging and a test for the Wasm name table.

[ncw]

PS. I'm adding Sam as reviewer on all these Phabricator reviews, because he's listed in the CODE_OWNERS.TXT document. I'm happy to add other people too though!

[ruiu]

When linking a large program, you have millions of symbols, and inserting all of them into a set or a hash table is too time-consuming. One of the most important design decision when I made lld is to do only one hash table lookup for each symbol read from a file. We have the main symbol table, so we have no room for other hash table or a set.

This patch inserts all symbols to other set, which violates the design decision. You need to come up with a different design to keep lld fast.

I wonder why wasm doesn't allow symbols with the same name. Non-external symbols are usually referenced not by name but by their indices, no? Symbol names for local symbols are mostly for debugging. No programs should refer them by name, at least in ELF.

[sunfish]

For comparison, wabt is ok with duplicate names here (see here), so this may be a bug in binaryen.

[sbc100]

Duplicate names is fine I think. Which means this is a binaryen bug I think.

[sbc100]

Also, in my experiments with gcc local symbols names can be duplicates of each other in the ELF world.

I linked two object with a static foo function and I get:

$ nm testelf  | grep foo
00000000004004ed t foo
000000000040050e t foo

[ncw]

That was silly. I also did a test with standard x86 ELF - and I thought I'd observed name mangling. But now I've just repeated the test and it doesn't happen.

Sorry! Closing this, I only submitted it under the mistaken impression that it was matching ELF behaviour.

test/wasm/Inputs/local1.ll

+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown-wasm"
+
+define internal i32 @staticFn() {
+entry:
+    ret i32 0
+}
+
+define i32 @fn1() {
+entry:
+    %rv = call i32 @staticFn()
+    ret i32 %rv
+}

test/wasm/Inputs/local2.ll

+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown-wasm"
+
+define internal i32 @staticFn() {
+entry:
+    ret i32 0
+}
+
+define i32 @fn2() {
+entry:
+    %rv = call i32 @staticFn()
+    ret i32 %rv
+}

test/wasm/duplicate-static.ll

+; RUN: llc -filetype=obj %S/Inputs/local1.ll -o %t.o
+; RUN: llc -filetype=obj %S/Inputs/local2.ll -o %t2.o
+; RUN: lld -flavor wasm --entry '' -o %t.wasm %t.o %t2.o
+; RUN: obj2yaml %t.wasm | FileCheck %s
+
+; CHECK:        - Type:            CUSTOM
+; CHECK:          Name:            name
+; CHECK-NEXT:     FunctionNames:   
+; CHECK-NEXT:       - Index:           0
+; CHECK-NEXT:         Name:            staticFn
+; CHECK-NEXT:       - Index:           1
+; CHECK-NEXT:         Name:            fn1
+; CHECK-NEXT:       - Index:           2
+; CHECK-NEXT:         Name:            staticFn.2
+; CHECK-NEXT:       - Index:           3
+; CHECK-NEXT:         Name:            fn2

wasm/Writer.cpp

for (const OutputSegment *S : Segments) {
       writeUleb128(SubSection.getStream(), S->Alignment, "alignment");
       writeUleb128(SubSection.getStream(), 0, "flags");
     }
     SubSection.finalizeContents();
     SubSection.writeToStream(OS);
   }
 }
 
+static std::string budgeName(StringRef Name, llvm::StringSet<> *UsedNames) {
+  for (int i = 2; true; ++i) {
+    std::string BudgedName = (Name + Twine(".") + Twine(i)).str();
+    if (UsedNames->insert(BudgedName).second)
+      return BudgedName;
+  }
+}
+
 // Create the custom "name" section containing debug symbol names.
 void Writer::createNameSection() {
   // Create an array of all function sorted by function index space
   std::vector<const Symbol *> Names;
+  llvm::StringSet<> UsedNames;
 
   for (ObjFile *File : Symtab->ObjectFiles) {
     Names.reserve(Names.size() + File->getSymbols().size());
     for (Symbol *S : File->getSymbols()) {
       if (!S->isFunction() || S->isWeak() || S->WrittenToNameSec)
         continue;
+      if (!S->isLocal()) {
+        bool inserted = UsedNames.insert(S->getName()).second;
+        assert(inserted); // Cannot have duplicate non-local, non-weak symbols
+      }
       S->WrittenToNameSec = true;
       Names.emplace_back(S);
     }
   }
 
   SyntheticSection *Section = createSyntheticSection(WASM_SEC_CUSTOM, "name");
 
   std::sort(Names.begin(), Names.end(), [](const Symbol *A, const Symbol *B) {
     return A->getOutputIndex() < B->getOutputIndex();
   });
 
   SubSection FunctionSubsection(WASM_NAMES_FUNCTION);
   raw_ostream &OS = FunctionSubsection.getStream();
   writeUleb128(OS, Names.size(), "name count");
 
   // We have to iterate through the inputs twice so that all the imports
   // appear first before any of the local function names.
   for (const Symbol *S : Names) {
     writeUleb128(OS, S->getOutputIndex(), "func index");
-    writeStr(OS, S->getName(), "symbol name");
+    StringRef Name = S->getName();
+    std::string BudgedName;
+    if (S->isLocal() && !UsedNames.insert(Name).second)
+      Name = (BudgedName = budgeName(Name, &UsedNames));
+    writeStr(OS, Name, "symbol name");
   }
 
   FunctionSubsection.finalizeContents();
   FunctionSubsection.writeToStream(Section->getStream());
 }
 
 void Writer::writeHeader() {
   memcpy(Buffer->getBufferStart(), Header.data(), Header.size());