[ELF] Refactor ObjFile<ELFT>::initializeSymbols to enforce the invariant: InputFile::symbols has non null entry

[MaskRay]

Summary

Fixes PR46348.

ObjFile<ELFT>::initializeSymbols contains two symbol iteration loops:

for each symbol
  if non-inheriting && non-local
    fill in this->symbols[i]

for each symbol
  if local
    fill in this->symbols[i]
  else
    symbol resolution

Symbol resolution can trigger a duplicate symbol error which will call
InputSectionBase::getObjMsg to iterate over InputFile::symbols. If a
non-local symbol appears after the non-local symbol being resolved
(violating ELF spec), its this->symbols[i] entry has not been filled
in, InputSectionBase::getObjMsg will crash due to
dyn_cast<Defined>(nullptr).

To fix the bug, reorganize the two loops to ensure this->symbols is
complete before symbol resolution. This enforces the invariant:
InputFile::symbols has none null entry when InputFile::getSymbols() is called.

for each symbol
  if non-inheriting
    fill in this->symbols[i]

for each symbol starting from firstGlobal
  if non-local
    symbol resolution

Additionally, move the (non-local symbol in local part of .symtab)
diagnostic from Writer<ELFT>::copyLocalSymbols() to initializeSymbols().

[jhenderson]

Thanks for the fix! It looks reasonable to me, but before approving, I wanted to ask would we be better off emitting some kind of warning or error about the out-of-order list earlier on?

lld/ELF/InputSection.cpp

350 ↗

(On Diff #271268)

It might be worth a comment saying under what conditions b can be nullptr.

[grimar]

In D81988#2097485, @jhenderson wrote:

would we be better off emitting some kind of warning or error about the out-of-order list earlier on?

+1 to this question.

lld/test/ELF/invalid/broken-symtab-duplicate-symbol.test

2 ↗

(On Diff #271268)

I do not think you should mention the particular internal API names.
This comment should be more general probably. Like:

In this test we have a local symbol that follows a global one. This is not correct .... Check that ...

15 ↗

(On Diff #271268)

OSABI is not needed.

28 ↗

(On Diff #271268)

Seems there is a double spacing here and above (Sections).

[MaskRay]

In D81988#2097630, @grimar wrote:

In D81988#2097485, @jhenderson wrote:

would we be better off emitting some kind of warning or error about the out-of-order list earlier on?

+1 to this question.

This should be a separate change. llvm-readobj -s should emit a warning as well (like GNU readelf).

lld/test/ELF/invalid/broken-symtab-duplicate-symbol.test

2 ↗

(On Diff #271268)

This test is coupled with the implementation. If the implementation changes, we'll have to adjust the test. Exposing a bit of implementation may be fine to remind a reader to adjust the test. I'll amend the comment a bit.

[MaskRay]

Add comment to code. Improve test.

[jhenderson]

I think this is okay. LGTM, with nit.

lld/test/ELF/invalid/broken-symtab-duplicate-symbol.test

2 ↗

(On Diff #271387)

Nit: spurious '#' at end of line.

[grimar]

In D81988#2098351, @MaskRay wrote:

In D81988#2097630, @grimar wrote:

In D81988#2097485, @jhenderson wrote:

would we be better off emitting some kind of warning or error about the out-of-order list earlier on?

+1 to this question.

This should be a separate change. llvm-readobj -s should emit a warning as well (like GNU readelf).

Shouldn't we just error out early?

We have a few more places where we have this code pattern:

1. MapFile.cpp

https://github.com/llvm/llvm-project/blob/master/lld/ELF/MapFile.cpp#L54

2. InputSectionBase::getEnclosingFunction:

https://github.com/llvm/llvm-project/blob/master/lld/ELF/InputSection.cpp#L285

That code also uses dyn_cast<Defined>(b) and makes me wondering why do you want to support
this broken case instead of reporting an error much earlier? This ways seems we will not need to
fix all other places.

[MaskRay]

In D81988#2100226, @grimar wrote:

In D81988#2098351, @MaskRay wrote:

In D81988#2097630, @grimar wrote:

In D81988#2097485, @jhenderson wrote:

would we be better off emitting some kind of warning or error about the out-of-order list earlier on?

+1 to this question.

This should be a separate change. llvm-readobj -s should emit a warning as well (like GNU readelf).

Shouldn't we just error out early?

Yes.

We have a few more places where we have this code pattern:

1. MapFile.cpp

https://github.com/llvm/llvm-project/blob/master/lld/ELF/MapFile.cpp#L54

2. InputSectionBase::getEnclosingFunction:

https://github.com/llvm/llvm-project/blob/master/lld/ELF/InputSection.cpp#L285

That code also uses dyn_cast<Defined>(b) and makes me wondering why do you want to support
this broken case instead of reporting an error much earlier? This ways seems we will not need to
fix all other places.

The two functions are called in the relocation pass, which is very late and is not subject to the bug.
I do think we have a more serious issue which my original description failed to capture.
Updating...

[MaskRay]

Refactor ObjFile<ELFT>::initializeSymbols instead

[MaskRay]

Move a diagnostic from Writer to initializeSymbols

[grimar]

LGTM with a nit.

lld/ELF/InputFiles.cpp

1062

You can do:

if (eSym.getBinding() != STB_LOCAL) {

and inline STB_LOCAL value.

[jhenderson]

lld/ELF/InputFiles.cpp

1100

Isn't this going to result in reading every global symbol twice? That seems like a negative performance hit to me, and I'm not sure it's necessary either (the two loops could still be a single loop it seems to me).

lld/test/ELF/invalid/symtab-sh-info-dup.test

6

an null -> a null
to null pointer -> to a null pointer

[MaskRay]

lld/ELF/InputFiles.cpp

1100

There were two loops before and two loops now. After refactoring there is strictly less work: the second loops starts from firstGlobal (was 0).

(the two loops could still be a single loop it seems to me)

It will be very difficult.

[MaskRay]

Address comments

[jhenderson]

lld/ELF/InputFiles.cpp

1100

Ah, sorry, the way the diff lined up made it look like only one loop on the left. Thanks.

lld/ELF/InputFiles.cpp

 }
 
 // Initialize this->Symbols. this->Symbols is a parallel array as
 // its corresponding ELF symbol table.
 template <class ELFT> void ObjFile<ELFT>::initializeSymbols() {
   ArrayRef<Elf_Sym> eSyms = this->getELFSyms<ELFT>();
   this->symbols.resize(eSyms.size());
 
-  // Our symbol table may have already been partially initialized
+  // Fill in InputFile::symbols. Some entries have been initialized
   // because of LazyObjFile.
-  for (size_t i = 0, end = eSyms.size(); i != end; ++i)
-    if (!this->symbols[i] && eSyms[i].getBinding() != STB_LOCAL)
-      this->symbols[i] =
-          symtab->insert(CHECK(eSyms[i].getName(this->stringTable), this));
-
-  // Fill this->Symbols. A symbol is either local or global.
   for (size_t i = 0, end = eSyms.size(); i != end; ++i) {
+    if (this->symbols[i])
+      continue;
     const Elf_Sym &eSym = eSyms[i];
-
-    // Read symbol attributes.
     uint32_t secIdx = getSectionIndex(eSym);
     if (secIdx >= this->sections.size())
       fatal(toString(this) + ": invalid section index: " + Twine(secIdx));
-
-    InputSectionBase *sec = this->sections[secIdx];
-    uint8_t binding = eSym.getBinding();
-    uint8_t stOther = eSym.st_other;
-    uint8_t type = eSym.getType();
-    uint64_t value = eSym.st_value;
-    uint64_t size = eSym.st_size;
-    StringRefZ name = this->stringTable.data() + eSym.st_name;
+    if (eSym.getBinding() != STB_LOCAL) {
+      if (i < firstGlobal)
+        error(toString(this) + ": non-local symbol (" + Twine(i) +
+              ") found at index < .symtab's sh_info (" + Twine(firstGlobal) +
+              ")");
+      this->symbols[i] =
+          symtab->insert(CHECK(eSyms[i].getName(this->stringTable), this));
+      continue;
+    }
 
     // Handle local symbols. Local symbols are not added to the symbol
     // table because they are not visible from other object files. We
-    // allocate symbol instances and add their pointers to Symbols.
-    if (binding == STB_LOCAL) {
-      if (eSym.getType() == STT_FILE)
-        sourceFile = CHECK(eSym.getName(this->stringTable), this);
+    // allocate symbol instances and add their pointers to symbols.
+    if (i >= firstGlobal)
+      errorOrWarn(toString(this) + ": STB_LOCAL symbol (" + Twine(i) +
+                  ") found at index >= .symtab's sh_info (" +
+                  Twine(firstGlobal) + ")");
 
-      if (this->stringTable.size() <= eSym.st_name)
-        fatal(toString(this) + ": invalid symbol name offset");
+    InputSectionBase *sec = this->sections[secIdx];
+    uint8_t type = eSym.getType();
+    if (type == STT_FILE)
+      sourceFile = CHECK(eSym.getName(this->stringTable), this);
+    StringRefZ name = this->stringTable.data() + eSym.st_name;
 
-      if (eSym.st_shndx == SHN_UNDEF)
-        this->symbols[i] = make<Undefined>(this, name, binding, stOther, type);
-      else if (sec == &InputSection::discarded)
-        this->symbols[i] = make<Undefined>(this, name, binding, stOther, type,
-                                           /*DiscardedSecIdx=*/secIdx);
-      else
-        this->symbols[i] =
-            make<Defined>(this, name, binding, stOther, type, value, size, sec);
-      continue;
-    }
+      this->symbols[i] =
+          make<Undefined>(this, name, STB_LOCAL, eSym.st_other, type);
+          make<Undefined>(this, name, STB_LOCAL, eSym.st_other, type,
+                          /*discardedSecIdx=*/secIdx);
+    else
+      this->symbols[i] = make<Defined>(this, name, STB_LOCAL, eSym.st_other,
+                                       type, eSym.st_value, eSym.st_size, sec);
 
+  // Symbol resolution of non-local symbols.
+  for (size_t i = firstGlobal, end = eSyms.size(); i != end; ++i) {
+    const Elf_Sym &eSym = eSyms[i];
+    uint8_t binding = eSym.getBinding();
+    if (binding == STB_LOCAL)
+      continue; // Errored above.
+
+    uint32_t secIdx = getSectionIndex(eSym);
+    InputSectionBase *sec = this->sections[secIdx];
+    uint8_t stOther = eSym.st_other;
+    uint8_t type = eSym.getType();
+    uint64_t value = eSym.st_value;
+    uint64_t size = eSym.st_size;
+    StringRefZ name = this->stringTable.data() + eSym.st_name;
+
     // Handle global undefined symbols.
     if (eSym.st_shndx == SHN_UNDEF) {
       this->symbols[i]->resolve(Undefined{this, name, binding, stOther, type});
       this->symbols[i]->referenced = true;
       continue;
     }
 
     // Handle global common symbols.

lld/ELF/Writer.cpp

 template <class ELFT> void Writer<ELFT>::copyLocalSymbols() {
   if (!in.symTab)
     return;
   if (config->copyRelocs && config->discard != DiscardPolicy::None)
     markUsedLocalSymbols<ELFT>();
   for (InputFile *file : objectFiles) {
     ObjFile<ELFT> *f = cast<ObjFile<ELFT>>(file);
     for (Symbol *b : f->getLocalSymbols()) {
-      if (!b->isLocal())
-        fatal(toString(f) +
-              ": broken object: getLocalSymbols returns a non-local symbol");
+      assert(b->isLocal() && "should have been caught in initializeSymbols()");
       auto *dr = dyn_cast<Defined>(b);
 
       // No reason to keep local undefined symbol in symtab.
       if (!dr)
         continue;
       if (!includeInSymtab(*b))
         continue;
       if (!shouldKeepInSymtab(*dr))

lld/test/ELF/invalid/symtab-sh-info-dup.test

+# REQUIRES: x86
+## The ELF spec says all symbols with STB_LOCAL binding precede the weak and
+## global symbols. If a local symbol is found in the non-local part of the
+## symbol table, make sure we have filled in all entries of InputFile::symbols.
+## Otherwise a null entry can lead to a null pointer dereference when iterating
+## over InputFile::symbols.
+
+# RUN: yaml2obj %s -o %t.o
+# RUN: not ld.lld %t.o %t.o -o /dev/null 2>&1 | FileCheck %s
+
+# CHECK:      error: {{.*}}.o: STB_LOCAL symbol (2) found at index >= .symtab's sh_info (1)
+# CHECK-NEXT: error: {{.*}}.o: STB_LOCAL symbol (2) found at index >= .symtab's sh_info (1)
+# CHECK-NEXT: error: duplicate symbol: _start
+# CHECK-NEXT: >>> defined at {{.*}}.o:(.text+0x0)
+# CHECK-NEXT: >>> defined at {{.*}}.o:(.text+0x0)
+
+# RUN: ld.lld --noinhibit-exec %t.o -o /dev/null 2>&1 | FileCheck %s --check-prefix=WARN
+# WARN: warning: {{.*}}.o: STB_LOCAL symbol (2) found at index >= .symtab's sh_info (1)
+
+!ELF
+FileHeader:
+  Class:   ELFCLASS64
+  Data:    ELFDATA2LSB
+  Type:    ET_REL
+  Machine: EM_X86_64
+Sections:
+  - Type:  SHT_PROGBITS
+    Name:  .text
+    Flags: [ SHF_ALLOC, SHF_EXECINSTR ]
+Symbols:
+  - Name:    _start
+    Section: .text
+    Binding: STB_GLOBAL
+  - Name:    local
+    Section: .text
+    Binding: STB_LOCAL

lld/test/ELF/invalid/symtab-sh-info.s

- Name:            .symtab
     Type:            SHT_SYMTAB
 Symbols:
   - Name:          foo
     Binding:       STB_GLOBAL
 
 ## sh_info has value 2 what says that non-local symbol `foo` is local.
 ## Check we report this case.
 # RUN: yaml2obj --docnum=2 %s -o %t.o
-# RUN: not ld.lld %t.o -o /dev/null 2>&1 | FileCheck --check-prefix=ERR2 %s
-# ERR2: broken object: getLocalSymbols returns a non-local symbol
+# RUN: not ld.lld --noinhibit-exec %t.o -o /dev/null 2>&1 | FileCheck --check-prefix=ERR2 %s
+# ERR2: error: {{.*}}.o: non-local symbol (1) found at index < .symtab's sh_info (2)
 
 --- !ELF
 FileHeader:
   Class:           ELFCLASS64
   Data:            ELFDATA2LSB
   Type:            ET_REL
   Machine:         EM_X86_64
 Sections: