[ELF] - Prevent relocation overflow against .bss in some cases.

[grimar]

Summary

This is https://bugs.llvm.org/show_bug.cgi?id=38037

When we add files:
https://github.com/llvm-mirror/lld/blob/master/ELF/Driver.cpp#L1267

We might add "COMMON" input sections, which are later
changes their name to ".bss" (in getOutputSectionName):
https://github.com/llvm-mirror/lld/blob/master/ELF/SymbolTable.cpp#L461
and placed to ".bss" output section.

Since we are adding the files first,
it results in such ".bss" created out of order and placed
at the start. Itself it is not a huge issue, perhaps, but the problem
appears when such "COMMON" sections (common symbols) are huge.

In PR, usr/lib/gcc/x86_64-linux-gnu/5.4.0/crtbegin.o is the first
in the command line and it has a R_X86_64_PC32 relocation against its own ".bss".
But because of LLD, which places huge input ".bss" created for user's SHN_COMMON symbol
at the beginning of the output section, relocation overflows.

The patch fixes the issue by moving all early created synthetics to the end of the input sections list.

[ruiu]

I doubt if the benefit of this patch exceeds the increased complexity. Isn't this a corner case where no one can really say this is a bug? Can't you simply fix your linker script instead of lld?

[grimar]

In D48924#1153414, @ruiu wrote:

I doubt if the benefit of this patch exceeds the increased complexity. Isn't this a corner case where no one can really say this is a bug?

GNU linkers have no problems with supporting that. If the user wants to create a large common symbol, why not?
It is an unlucky specific of our implementation that we create "COMMON" input sections out of order in the first place.
If we would create sections in the same order as objects are specified in the command line, we would not have this issue.

Isn't another our patches that try to workaround possible relocations overflow do something the same (reordering the sections)?

Can't you simply fix your linker script instead of lld?

There is no linker script used in the initial PR.

ELF/Driver.cpp

template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   // files" and not object files. Index file creation is already done
   // in addCombinedLTOObject, so we are done if that's the case.
   if (Config->ThinLTOIndexOnly)
     return;
 
   // Apply symbol renames for -wrap.
   Symtab->applySymbolWrap();
 
-  // Now that we have a complete list of input files.
-  // Beyond this point, no new files are added.
-  // Aggregate all input sections into one place.
+  // Now that we have a complete list of input files. Beyond this point, no new
+  // files are added. Aggregate all input sections into one place.
+  //
+  // At this point, the list might be not empty and contain synthetic sections
+  // created for common symbols. We want to move them to the end of input
+  // sections list. That way they will be grouped with other synthetics we will
+  // add. This helps sometimes to resolve relocations properly. For example,
+  // gcc/x86_64-linux-gnu/5.4.0/crtbegin.o has 32bit relocation against it's
+  // own .bss. If user's code has huge common symbol, it would be placed at the
+  // start of ".bss" and may cause overflow.
+  std::vector<InputSectionBase *> Commons;
+  Commons.swap(InputSections);
   for (InputFile *F : ObjectFiles)
     for (InputSectionBase *S : F->getSections())
       if (S && S != &InputSection::Discarded)
         InputSections.push_back(S);
   for (BinaryFile *F : BinaryFiles)
     for (InputSectionBase *S : F->getSections())
       InputSections.push_back(cast<InputSection>(S));
+  for (InputSectionBase *S : Commons)
+    InputSections.push_back(S);
 
   // We do not want to emit debug sections if --strip-all
   // or -strip-debug are given.
   if (Config->Strip != StripPolicy::None)
     llvm::erase_if(InputSections, [](InputSectionBase *S) {
       return S->Name.startswith(".debug") || S->Name.startswith(".zdebug");
     });
 

test/ELF/bss-reloc-overflow.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t2
+
+## Previously we were not able to link this code.
+## It has R_X86_64_PC32 relocation which overflowed.
+
+.text
+.long .bss - .
+
+.bss
+.byte 0x0
+
+.type arr,@object
+.comm arr,0xffffffff,4