[ELF] compareByFilePosition requires stable_sort

[smeenai]

Summary

The comment at the top of compareByFilePosition indicates that it relies
on stable_sort to preserve the order of synthetic sections. We were
using sort instead of stable_sort, however, leading to incorrect
synthetic section ordering.

[smeenai]

I discovered this because the .ARM.exidx end sentinel was getting incorrectly reordered away from the end of the section, leading to unwinding failing in certain binaries. CC @peter.smith, in case you've run into any similar issues.

Unfortunately, I'm not sure how to write a test case for this. I was using -ffunction-sections so I would end up with multiple .ARM.exidx.* sections, so there's a reasonable chance of the sentinel getting incorrectly reordered, but there's no guarantee, since it depends on the underlying std::sort implementation (which could potentially even be randomized). Any ideas?

[peter.smith]

In D35473#811101, @smeenai wrote:

I discovered this because the .ARM.exidx end sentinel was getting incorrectly reordered away from the end of the section, leading to unwinding failing in certain binaries. CC @peter.smith, in case you've run into any similar issues.

Unfortunately, I'm not sure how to write a test case for this. I was using -ffunction-sections so I would end up with multiple .ARM.exidx.* sections, so there's a reasonable chance of the sentinel getting incorrectly reordered, but there's no guarantee, since it depends on the underlying std::sort implementation (which could potentially even be randomized). Any ideas?

I've not seen this myself, but I haven't done a lot of testing on this after the initial patch went in, which I think was stable_sort at the time. I agree it will be difficult to write a test that will trigger reliably on all platforms sort routine. I've no objections to the change, although it might be better to rewrite compareByFilePosition to be std::sort friendly. For example it is currently:

static bool compareByFilePosition(InputSection *A, InputSection *B) {
  // Synthetic doesn't have link order dependecy, stable_sort will keep it last
  if (A->kind() == InputSectionBase::Synthetic ||
      B->kind() == InputSectionBase::Synthetic)
    return false;
  InputSection *LA = A->getLinkOrderDep();
  InputSection *LB = B->getLinkOrderDep();
  OutputSection *AOut = LA->getParent();
  OutputSection *BOut = LB->getParent();
  if (AOut != BOut)
    return AOut->SectionIndex < BOut->SectionIndex;
  return LA->OutSecOff < LB->OutSecOff;
}

I think it could be rewritten as:

static bool compareByFilePosition(InputSection *A, InputSection *B) {
  // Only Synthetic with a link order dependency is the ARMExidxSentinelSection
  // There is only one of these and it must be last.
  if (A->kind() == InputSectionBase::Synthetic)
    return false;
  if (B->kind() == InputSectionBase::Synthetic)
    return true;
  InputSection *LA = A->getLinkOrderDep();
  InputSection *LB = B->getLinkOrderDep();
  OutputSection *AOut = LA->getParent();
  OutputSection *BOut = LB->getParent();
  if (AOut != BOut)
    return AOut->SectionIndex < BOut->SectionIndex;
  return LA->OutSecOff < LB->OutSecOff;
}

[smeenai]

@peter.smith Yeah changing compareByFilePosition should work for now, though stable_sort might be more future-proof. I'll leave that for @rafael and @ruiu to decide.

[ruiu]

LGTM

ELF/LinkerScript.cpp

1087

I think you don't have to write this comment here, as we use std::stable_sort everywhere for reproducibility.

[smeenai]

ELF/LinkerScript.cpp

1087

I'll remove it before committing.

ELF/LinkerScript.cpp

template <class ELFT> void OutputSectionCommand::finalize() {
   for (BaseCommand *Base : Commands)
     if (auto *ISD = dyn_cast<InputSectionDescription>(Base))
       for (InputSection *&IS : ISD->Sections) {
         ScriptSections.push_back(&IS);
         Sections.push_back(IS);
       }
 
   if ((Sec->Flags & SHF_LINK_ORDER)) {
-    std::sort(Sections.begin(), Sections.end(), compareByFilePosition);
+    // compareByFilePosition requires stable_sort (see comment in it).
+    std::stable_sort(Sections.begin(), Sections.end(), compareByFilePosition);
     for (int I = 0, N = Sections.size(); I < N; ++I)
       *ScriptSections[I] = Sections[I];
 
     // 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 *D = Sections.front()->getLinkOrderDep())