[ELF] compareByFilePosition requires stable_sort
ClosedPublic

Authored by smeenai on Jul 17 2017, 12:04 AM.

Details

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.

Diff Detail

Repository
rL LLVM
smeenai created this revision.Jul 17 2017, 12:04 AM

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 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;
}

@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 accepted this revision.Jul 17 2017, 10:53 AM

LGTM

ELF/LinkerScript.cpp
1087 ↗(On Diff #106836)

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

This revision is now accepted and ready to land.Jul 17 2017, 10:53 AM
smeenai added inline comments.Jul 17 2017, 12:40 PM
ELF/LinkerScript.cpp
1087 ↗(On Diff #106836)

I'll remove it before committing.

This revision was automatically updated to reflect the committed changes.