[ELF] - Linkerscript: PR30387 - cannot handle EXCLUDE_FILE in the middle of a input section description.

[grimar]

Summary

This is PR30387:

From PR description:
We fail to parse

SECTIONS
{
  foo :
  {
    *(sec0 EXCLUDE_FILE (zed1.o) sec1  EXCLUDE_FILE (zed2.o) sec2 )
  }
}

The semantics according to bfd are:

• Include sec1 from every file but zed1.o
• Include sec2 from every file but zed2.o
• Include sec0 from every file

Patch implements the support.

[• rafael]

LGTM with nits.

ELF/LinkerScript.cpp

989 ↗

(On Diff #71602)

Add a comment saying what this parses, which i think is

((EXCLUDE_FILE(file_patterrn+))? section_pattern+)+

990 ↗

(On Diff #71602)

The default constructed RE matches anything?

[grimar]

ELF/LinkerScript.cpp

990 ↗

(On Diff #71602)

Nope, even do not tries, returns no match found instantly as it is in "error state".

[grimar]

I am observing bot failures on next two bots:
http://lab.llvm.org:8011/builders/lld-x86_64-freebsd/builds/21301/steps/build_Lld/logs/stdio
http://lab.llvm.org:8011/builders/lld-x86_64-darwin13/builds/27508/steps/build_Lld/logs/stdio

Compile issue does not appear on windows and llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast,
and according to error message it is just something broken in stl implementation.
I was able to reproduce it on FreeBSD VM I have and found it
does not like to have a pairs in a vector where at least one element of pair
has movable constructor and deleted copy constructor, like Regex has.
It tries to call copy constructor instead and errors out.

Next simple testcase demonstrates the issue.
class Test {
public:

Test() {};
Test(const Test &) = delete;
Test(Test &&) {}

};

...

std::vector<std::pair<Test, int>> XXX;
X.resize(1);

...

/usr/include/c++/v1/utility:283:11: error: call to deleted constructor of 'Test'
        : first(__p.first),
          ^     ~~~~~~~~~
/usr/include/c++/v1/memory:1645:31: note: in instantiation of member function 'std::__1::pair<Test, int>::pair' requested here
            ::new((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);
                              ^
/usr/include/c++/v1/memory:1572:18: note: in instantiation of function template specialization 'std::__1::allocator<std::__1::pair<Test, int> >::construct<std::__1::pair<Test, int>, const std::__1::pair<Test, int> &>' requested here
            {__a.construct(__p, _VSTD::forward<_Args>(__args)...);}
                 ^
/usr/include/c++/v1/memory:1453:14: note: in instantiation of function template specialization 'std::__1::allocator_traits<std::__1::allocator<std::__1::pair<Test, int> > >::__construct<std::__1::pair<Test, int>, const std::__1::pair<Test, int> &>' requested here
            {__construct(__has_construct<allocator_type, _Tp*, _Args...>(),
             ^
/usr/include/c++/v1/memory:1535:17: note: in instantiation of function template specialization 'std::__1::allocator_traits<std::__1::allocator<std::__1::pair<Test, int> > >::construct<std::__1::pair<Test, int>, const std::__1::pair<Test, int> &>' requested here
                construct(__a, _VSTD::__to_raw_pointer(__end2-1), _VSTD::move_if_noexcept(*--__end1));
                ^
/usr/include/c++/v1/vector:897:21: note: in instantiation of function template specialization 'std::__1::allocator_traits<std::__1::allocator<std::__1::pair<Test, int> > >::__construct_backward<std::__1::pair<Test, int> *>' requested here
    __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
                    ^
/usr/include/c++/v1/vector:1051:9: note: in instantiation of member function 'std::__1::vector<std::__1::pair<Test, int>, std::__1::allocator<std::__1::pair<Test, int> > >::__swap_out_circular_buffer' requested here
        __swap_out_circular_buffer(__v);
        ^
/usr/include/c++/v1/vector:1999:15: note: in instantiation of member function 'std::__1::vector<std::__1::pair<Test, int>, std::__1::allocator<std::__1::pair<Test, int> > >::__append' requested here
        this->__append(__sz - __cs);
              ^
/root/LLVM/llvm/tools/lld/ELF/LinkerScript.cpp:1037:6: note: in instantiation of member function 'std::__1::vector<std::__1::pair<Test, int>, std::__1::allocator<std::__1::pair<Test, int> > >::resize' requested here
 XXX.resize(1);
     ^
/root/LLVM/llvm/tools/lld/ELF/LinkerScript.cpp:1022:3: note: function has been explicitly marked deleted here
  Test(const Test &) = delete;

Workaround I found is just use stl::list instead std::vector. Since it is almost always container of 1 elements for this case, it should work the same good and I going to recommit it with this fix.

[ruiu]

lld/trunk/ELF/LinkerScript.cpp

992

It's not clear to me what the grammar of this thing is.

A B EXCLUDE_FILE(C) D E

Does the above pattern mean A, B, D except those matching C, and E? Or A, B, D except those matching C, E except those matching C?

What if the pattern is this?

A B EXCLUDE_FILE(C) EXCLUDE_FILE(D) E

[grimar]

lld/trunk/ELF/LinkerScript.cpp

992

Example from PR30387:

sec0 EXCLUDE_FILE (zed1.o) sec1 EXCLUDE_FILE (zed2.o) sec2 )

The semantics according to bfd are:
Include sec1 from every file but zed1.o
Include sec2 from every file but zed2.o
Include sec0 from every file

So

A B EXCLUDE_FILE(C) D E

Should be all A, B sections + all D, E excluding those in file C.

Pattern of

A B EXCLUDE_FILE(C) EXCLUDE_FILE(D) E

then should be all A, B + all E except those in file E.

[grimar]

lld/trunk/ELF/LinkerScript.cpp

992

Fix for last:
A B EXCLUDE_FILE(C) EXCLUDE_FILE(D) E
then should be all A, B + all E except those in file D.

[ruiu]

lld/trunk/ELF/LinkerScript.cpp

992

I think two consecutve EXCLUDE_FILEs are more like a syntax error than a valid grammar, no? Is there any reason you want to accept it?

[ruiu]

I just spent a few hours to clean up the linker script code and realized that it is getting hard to read because of lack of comments. There are bunch of functions and variables that are not obvious about what they are for, and the only way to understand it is reading code. The code may be easy to read if you already know what the code is doing, but our bar should be higher. I'll add more comments and refactor for simplification, but please write more comments in the first place to describe what you are trying to do for what purpose.

[grimar]

In D24650#545515, @ruiu wrote:

I just spent a few hours to clean up the linker script code and realized that it is getting hard to read because of lack of comments. There are bunch of functions and variables that are not obvious about what they are for, and the only way to understand it is reading code. The code may be easy to read if you already know what the code is doing, but our bar should be higher. I'll add more comments and refactor for simplification, but please write more comments in the first place to describe what you are trying to do for what purpose.

Sure, I will write more comments in future.

lld/trunk/ELF/LinkerScript.cpp

992

Aim was to support example from PR30387 (so case from testcase).
I thought you're asking how it works here (and believed bfd accepts the same),
but today found it is do not like consecutve EXCLUDE_FILEs. I can prepare a patch.

lld/trunk/ELF/LinkerScript.h

 struct InputSectionDescription : BaseCommand {
   InputSectionDescription(StringRef FilePattern)
       : BaseCommand(InputSectionKind),
         FileRe(compileGlobPatterns({FilePattern})) {}
   static bool classof(const BaseCommand *C);
   llvm::Regex FileRe;
   SortKind SortOuter = SortNone;
   SortKind SortInner = SortNone;
-  llvm::Regex ExcludedFileRe;
-  llvm::Regex SectionRe;
+  // Pairs of section regex and files excluded.
+  std::vector<std::pair<llvm::Regex, llvm::Regex>> SectionsVec;
 };
 
 struct AssertCommand : BaseCommand {
   AssertCommand(Expr E) : BaseCommand(AssertKind), Expression(E) {}
   static bool classof(const BaseCommand *C);
   Expr Expression;
 };
 

lld/trunk/ELF/LinkerScript.cpp

 template <class ELFT>
 bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
   for (Regex *Re : Opt.KeptSections)
     if (Re->match(S->Name))
       return true;
   return false;
 }
 
-static bool fileMatches(const InputSectionDescription *Desc,
-                        StringRef Filename) {
-  return const_cast<Regex &>(Desc->FileRe).match(Filename) &&
-         !const_cast<Regex &>(Desc->ExcludedFileRe).match(Filename);
+static bool fileMatches(const llvm::Regex &FileRe,
+                        const llvm::Regex &ExcludedFileRe, StringRef Filename) {
+  return const_cast<Regex &>(FileRe).match(Filename) &&
+         !const_cast<Regex &>(ExcludedFileRe).match(Filename);
 }
 
 static bool comparePriority(InputSectionData *A, InputSectionData *B) {
   return getPriority(A->Name) < getPriority(B->Name);
 }
 
 static bool compareName(InputSectionData *A, InputSectionData *B) {
   return A->Name < B->Name;
return llvm::all_of(Sections, [=](InputSectionBase<ELFT> *Sec) {
     return checkConstraint(Sec->getSectionHdr()->sh_flags, Kind);
   });
 }
 
 // Returns input sections filtered by given glob patterns.
 template <class ELFT>
 std::vector<InputSectionBase<ELFT> *>
 LinkerScript<ELFT>::getInputSections(const InputSectionDescription *I) {
-  const Regex &Re = I->SectionRe;
   std::vector<InputSectionBase<ELFT> *> Ret;
-  for (ObjectFile<ELFT> *F : Symtab<ELFT>::X->getObjectFiles())
-    if (fileMatches(I, sys::path::filename(F->getName())))
+  for (const std::pair<llvm::Regex, llvm::Regex> &V : I->SectionsVec) {
+    for (ObjectFile<ELFT> *F : Symtab<ELFT>::X->getObjectFiles()) {
+      if (fileMatches(I->FileRe, V.first, sys::path::filename(F->getName()))) {
+
+        Regex &Re = const_cast<Regex &>(V.second);
         for (InputSectionBase<ELFT> *S : F->getSections())
-        if (!isDiscarded(S) && !S->OutSec &&
-            const_cast<Regex &>(Re).match(S->Name))
+          if (!isDiscarded(S) && !S->OutSec && Re.match(S->Name))
             Ret.push_back(S);
 
-  if (const_cast<Regex &>(Re).match("COMMON"))
+        if (Re.match("COMMON"))
           Ret.push_back(CommonInputSection<ELFT>::X);
+      }
+    }
+  }
   return Ret;
 }
 
 template <class ELFT>
 void LinkerScript<ELFT>::discard(ArrayRef<InputSectionBase<ELFT> *> V) {
   for (InputSectionBase<ELFT> *S : V) {
     S->Live = false;
     reportDiscarded(S);
private:
 
   SymbolAssignment *readAssignment(StringRef Name);
   std::vector<uint8_t> readFill();
   OutputSectionCommand *readOutputSectionDescription(StringRef OutSec);
   std::vector<uint8_t> readOutputSectionFiller(StringRef Tok);
   std::vector<StringRef> readOutputSectionPhdrs();
   InputSectionDescription *readInputSectionDescription(StringRef Tok);
   Regex readFilePatterns();
+  void readSectionExcludes(InputSectionDescription *Cmd);
   InputSectionDescription *readInputSectionRules(StringRef FilePattern);
   unsigned readPhdrType();
   SortKind readSortKind();
   SymbolAssignment *readProvideHidden(bool Provide, bool Hidden);
   SymbolAssignment *readProvideOrAssignment(StringRef Tok, bool MakeAbsolute);
   void readSort();
   Expr readAssert();
 
if (skip("SORT") || skip("SORT_BY_NAME"))
     return SortByName;
   if (skip("SORT_BY_ALIGNMENT"))
     return SortByAlignment;
   if (skip("SORT_BY_INIT_PRIORITY"))
     return SortByPriority;
   return SortNone;
 }
 
-InputSectionDescription *
-ScriptParser::readInputSectionRules(StringRef FilePattern) {
-  auto *Cmd = new InputSectionDescription(FilePattern);
-  expect("(");
+// Method reads a list of sequence of excluded files and section globs given in
+// a following form: ((EXCLUDE_FILE(file_pattern+))? section_pattern+)+
+// Example: *(.foo.1 EXCLUDE_FILE (*a.o) .foo.2 EXCLUDE_FILE (*b.o) .foo.3)
+void ScriptParser::readSectionExcludes(InputSectionDescription *Cmd) {
+  llvm::Regex ExcludeFileRe;
+  std::vector<StringRef> V;
+
+  while (!Error) {
+    if (skip(")")) {
+      Cmd->SectionsVec.push_back(
+          {std::move(ExcludeFileRe), compileGlobPatterns(V)});
+      return;
+    }
 
-  // Read EXCLUDE_FILE().
     if (skip("EXCLUDE_FILE")) {
+      if (!V.empty()) {
+        Cmd->SectionsVec.push_back(
+            {std::move(ExcludeFileRe), compileGlobPatterns(V)});
+        V.clear();
+      }
+
       expect("(");
-    Cmd->ExcludedFileRe = readFilePatterns();
+      ExcludeFileRe = readFilePatterns();
+      continue;
+    }
+
+    V.push_back(next());
   }
+}
+
+InputSectionDescription *
+ScriptParser::readInputSectionRules(StringRef FilePattern) {
+  auto *Cmd = new InputSectionDescription(FilePattern);
+  expect("(");
 
   // Read SORT().
   if (SortKind K1 = readSortKind()) {
     Cmd->SortOuter = K1;
     expect("(");
     if (SortKind K2 = readSortKind()) {
       Cmd->SortInner = K2;
       expect("(");
-      Cmd->SectionRe = readFilePatterns();
+      Cmd->SectionsVec.push_back({llvm::Regex(), readFilePatterns()});
       expect(")");
     } else {
-      Cmd->SectionRe = readFilePatterns();
+      Cmd->SectionsVec.push_back({llvm::Regex(), readFilePatterns()});
     }
     expect(")");
     return Cmd;
   }
 
-  Cmd->SectionRe = readFilePatterns();
+  readSectionExcludes(Cmd);
   return Cmd;
 }
 
 InputSectionDescription *
 ScriptParser::readInputSectionDescription(StringRef Tok) {
   // Input section wildcard can be surrounded by KEEP.
   // https://sourceware.org/binutils/docs/ld/Input-Section-Keep.html#Input-Section-Keep
   if (Tok == "KEEP") {
     expect("(");
     StringRef FilePattern = next();
     InputSectionDescription *Cmd = readInputSectionRules(FilePattern);
     expect(")");
-    Opt.KeptSections.push_back(&Cmd->SectionRe);
+    for (std::pair<llvm::Regex, llvm::Regex> &Regex : Cmd->SectionsVec)
+      Opt.KeptSections.push_back(&Regex.second);
     return Cmd;
   }
   return readInputSectionRules(Tok);
 }
 
 void ScriptParser::readSort() {
   expect("(");
   expect("CONSTRUCTORS");

lld/trunk/test/ELF/linkerscript/Inputs/exclude-multiple1.s

+.section .foo.1,"a"
+ .quad 4
+
+.section .foo.2,"a"
+ .quad 5
+
+.section .foo.3,"a"
+ .quad 6

lld/trunk/test/ELF/linkerscript/Inputs/exclude-multiple2.s

+.section .foo.1,"a"
+ .quad 7
+
+.section .foo.2,"a"
+ .quad 8
+
+.section .foo.3,"a"
+ .quad 9

lld/trunk/test/ELF/linkerscript/exclude-multiple.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %tfile1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/exclude-multiple1.s -o %tfile2.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/exclude-multiple2.s -o %tfile3.o
+# RUN: echo "SECTIONS { \
+# RUN:   .foo : { *(.foo.1 EXCLUDE_FILE (*file1.o) .foo.2 EXCLUDE_FILE (*file2.o) .foo.3) } \
+# RUN:  }" > %t1.script
+# RUN: ld.lld -script %t1.script %tfile1.o %tfile2.o %tfile3.o -o %t1.o
+# RUN: llvm-objdump -s %t1.o | FileCheck %s
+
+# CHECK:      Contents of section .foo:
+# CHECK-NEXT:  0120 01000000 00000000 04000000 00000000
+# CHECK-NEXT:  0130 07000000 00000000 05000000 00000000
+# CHECK-NEXT:  0140 08000000 00000000 03000000 00000000
+# CHECK-NEXT:  0150 09000000 00000000
+# CHECK-NEXT: Contents of section .foo.2:
+# CHECK-NEXT:  0158 02000000 00000000
+# CHECK-NEXT: Contents of section .foo.3:
+# CHECK-NEXT:  0160 06000000 00000000
+
+.section .foo.1,"a"
+ .quad 1
+
+.section .foo.2,"a"
+ .quad 2
+
+.section .foo.3,"a"
+ .quad 3