[ELF] Allow SHF_LINK_ORDER and non-SHF_LINK_ORDER to be mixed

[MaskRay]

Summary

Currently, error: incompatible section flags for .rodata is reported
when we mix SHF_LINK_ORDER and non-SHF_LINK_ORDER sections in an output section.

This is overconstrained. This patch allows mixed flags with the
requirement that SHF_LINK_ORDER sections must be contiguous. Mixing
flags is used by Linux aarch64 (https://github.com/ClangBuiltLinux/linux/issues/953)

.init.data : { ... KEEP(*(__patchable_function_entries)) ... }

When the integrated assembler is enabled, clang's -fpatchable-function-entry=N[,M]
implementation sets the SHF_LINK_ORDER flag (D72215) to fix a number of
garbage collection issues.

Strictly speaking, the ELF specification does not require contiguous
SHF_LINK_ORDER sections but for many current uses of SHF_LINK_ORDER like
.ARM.exidx/__patchable_function_entries there has been a requirement for
the sections to be contiguous on top of the requirements of the ELF
specification.

This patch also imposes one restriction: SHF_LINK_ORDER sections cannot
be separated by a symbol assignment or a BYTE command. Not allowing BYTE is a natural
extension that a non-SHF_LINK_ORDER cannot be a separator.
Symbol assignments can delimiter the contents of SHF_LINK_ORDER sections.
Allowing SHF_LINK_ORDER sections cross symbol assignments (e.g. start_/stop_) can make things hard to explain.

[psmith]

I agree that there is no reason not to support the mixing of SHF_LINK_ORDER and non SHF_LINK_ORDER in the same OutputSection. Arm's proprietary linker will handle .ARM.exidx that way, I believe that a separate OutputSection is used in GNU ld and LLD as it simplifies the generation of Linker Generated Symbols that the library uses to find the tables.

Strictly speaking I don't think that there is anything in the ELF spec that requires that SHF_LINK_ORDER sections be contiguous.

This flag adds special ordering requirements for link editors. The requirements apply if the sh_link field of this section's header references another section (the linked-to section). If this section is combined with other sections in the output file, it must appear in the same relative order with respect to those sections, as the linked-to section appears with respect to sections the linked-to section is combined with.

In all current uses of SHF_LINK_ORDER like .ARM.exidx there has been a requirement for the sections to be contiguous on top of the requirements of the ELF specification so I'm happy to keep the diagnostic.

[MaskRay]

Incorporate some wording changes suggested by Peter

[MaskRay]

Improve test.
Mention -fpatchable-function-entry= sets SHF_LINK_ORDER only if integrated assembler is enabled

lld/ELF/OutputSections.cpp

if (!hasInputSections) {
     // If IS is the first section to be added to this section,
     // initialize type, entsize and flags from isec.
     hasInputSections = true;
     type = isec->type;
     entsize = isec->entsize;
     flags = isec->flags;
   } else {
     // Otherwise, check if new type or flags are compatible with existing ones.
-    unsigned mask = SHF_TLS | SHF_LINK_ORDER;
-    if ((flags & mask) != (isec->flags & mask))
+    if ((flags ^ isec->flags) & SHF_TLS)
       error("incompatible section flags for " + name + "\n>>> " + toString(isec) +
             ": 0x" + utohexstr(isec->flags) + "\n>>> output section " + name +
             ": 0x" + utohexstr(flags));
 
     if (type != isec->type) {
       if (!canMergeToProgbits(type) || !canMergeToProgbits(isec->type))
         error("section type mismatch for " + isec->name + "\n>>> " +
               toString(isec) + ": " +
void OutputSection::finalize() {
 
   if (flags & SHF_LINK_ORDER) {
     // We must preserve the link order dependency of sections with the
     // SHF_LINK_ORDER flag. The dependency is indicated by the sh_link field. We
     // need to translate the InputSection sh_link to the OutputSection sh_link,
     // all InputSections in the OutputSection have the same dependency.
     if (auto *ex = dyn_cast<ARMExidxSyntheticSection>(first))
       link = ex->getLinkOrderDep()->getParent()->sectionIndex;
-    else if (auto *d = first->getLinkOrderDep())
+    else if (first->flags & SHF_LINK_ORDER)
+      if (auto *d = first->getLinkOrderDep())
         link = d->getParent()->sectionIndex;
   }
 
   if (type == SHT_GROUP) {
     finalizeShtGroup(this, first);
     return;
   }
 
   if (!config->copyRelocs || (type != SHT_RELA && type != SHT_REL))

lld/ELF/Writer.cpp

for (OutputSection *sec : outputSections) {
     if (!config->relocatable && config->emachine == EM_ARM &&
         sec->type == SHT_ARM_EXIDX)
       continue;
 
     // Link order may be distributed across several InputSectionDescriptions
     // but sort must consider them all at once.
     std::vector<InputSection **> scriptSections;
     std::vector<InputSection *> sections;
+    bool started = false, stopped = false;
     for (BaseCommand *base : sec->sectionCommands) {
       if (auto *isd = dyn_cast<InputSectionDescription>(base)) {
         for (InputSection *&isec : isd->sections) {
+          if (!(isec->flags & SHF_LINK_ORDER)) {
+            if (started)
+              stopped = true;
+          } else if (stopped) {
+            error(toString(isec) + ": SHF_LINK_ORDER sections in " + sec->name +
+                  " are not contiguous");
+          } else {
+            started = true;
+
             scriptSections.push_back(&isec);
             sections.push_back(isec);
 
             InputSection *link = isec->getLinkOrderDep();
             if (!link->getParent())
               error(toString(isec) + ": sh_link points to discarded section " +
                     toString(link));
           }
         }
+      } else if (started) {
+        stopped = true;
+      }
     }
 
     if (errorCount())
       continue;
 
     llvm::stable_sort(sections, compareByFilePosition);
 
     for (int i = 0, n = sections.size(); i < n; ++i)

lld/test/ELF/linkerscript/linkorder.s

 
 # CHECK2:      [ 1] .rodata   {{.*}} AL 4
 # CHECK2:      [ 4] .text.bar {{.*}} AX 0
 # CHECK2:      Hex dump of section '.rodata':
 # CHECK2-NEXT: 0201
 
 ## Non-contiguous SHF_LINK_ORDER sections, separated by a BYTE.
 # RUN: echo 'SECTIONS { .rodata : {*(.rodata.foo) BYTE(0) *(.rodata.bar)} }' > %terr1.lds
-# RUN: ld.lld -T %terr1.lds %t.o -o /dev/null
+# RUN: not ld.lld -T %terr1.lds %t.o -o /dev/null 2>&1 | FileCheck --check-prefix=ERR %s
 
 ## Non-contiguous SHF_LINK_ORDER sections, separated by a non-SHF_LINK_ORDER section.
 # RUN: echo 'SECTIONS { .rodata : {*(.rodata.foo) *(.text) *(.rodata.bar)} }' > %terr2.lds
 # RUN: not ld.lld -T %terr2.lds %t.o -o /dev/null 2>&1 | FileCheck --check-prefix=ERR %s
 
 ## Non-contiguous SHF_LINK_ORDER sections, separated by a symbol assignment.
 # RUN: echo 'SECTIONS { .rodata : {*(.rodata.foo) a = .; *(.rodata.bar)} }' > %terr3.lds
-# RUN: ld.lld -T %terr3.lds %t.o -o /dev/null
+# RUN: not ld.lld -T %terr3.lds %t.o -o /dev/null 2>&1 | FileCheck --check-prefix=ERR %s
 
-# ERR: error: incompatible section flags for .rodata
+# ERR: error: {{.*}}.o:(.rodata.bar): SHF_LINK_ORDER sections in .rodata are not contiguous
 
 .global _start
 _start:
 
 .section .ro,"a"
 .byte 0
 
 .section .text.bar,"a",@progbits
 .byte 2
 .section .text.foo,"a",@progbits
 .byte 1
 .section .rodata.foo,"ao",@progbits,.text.foo
 .byte 1
 .section .rodata.bar,"ao",@progbits,.text.bar
 .byte 2