Relocations.cpp

      if (A->OutSecOff < B->OutSecOff)
        return true;
      if (A->OutSecOff == B->OutSecOff)
        // Check if Thunk is immediately before any specific Target InputSection
        // for example Mips LA25 Thunks.
        if (auto *TA = dyn_cast<ThunkSection>(A))
          if (TA && TA->getTargetInputSection() == B)
            return true;
      return false;
    };
    std::merge(ISR->begin(), ISR->end(), Thunks.begin(), Thunks.end(),
               std::back_inserter(Tmp), MergeCmp);
    *ISR = std::move(Tmp);
  }
}

static uint32_t findEndOfFirstNonExec(OutputSection &Cmd) {
  for (BaseCommand *Base : Cmd.Commands)
    if (auto *ISD = dyn_cast<InputSectionDescription>(Base))
      for (auto *IS : ISD->Sections)
        if ((IS->Flags & SHF_EXECINSTR) == 0)
          return IS->OutSecOff + IS->getSize();
  return 0;
}

ThunkSection *ThunkCreator::getOSThunkSec(OutputSection *OS,
                                          std::vector<InputSection *> *ISR) {
  if (CurTS == nullptr) {
    uint32_t Off = findEndOfFirstNonExec(*OS);
    CurTS = addThunkSection(OS, ISR, Off);
  }
  return CurTS;
}

// Add a Thunk that needs to be placed in a ThunkSection that immediately
// precedes its Target.
ThunkSection *ThunkCreator::getISThunkSec(InputSection *IS) {
  ThunkSection *TS = ThunkedSections.lookup(IS);
  if (TS)
    return TS;

  // Find InputSectionRange within Target Output Section (TOS) that the
  // InputSection (IS) that we need to precede is in.
  OutputSection *TOS = IS->getParent();
  std::vector<InputSection *> *Range = nullptr;
  for (BaseCommand *BC : TOS->Commands)
    if (auto *ISD = dyn_cast<InputSectionDescription>(BC)) {
      InputSection *first = ISD->Sections.front();
      InputSection *last = ISD->Sections.back();
      if (IS->OutSecOff >= first->OutSecOff &&
          IS->OutSecOff <= last->OutSecOff) {
        Range = &ISD->Sections;
        break;
      }
    }
  TS = addThunkSection(TOS, Range, IS->OutSecOff);
  ThunkedSections[IS] = TS;
  return TS;
}

ThunkSection *ThunkCreator::addThunkSection(OutputSection *OS,
                                            std::vector<InputSection *> *ISR,
                                            uint64_t Off) {
  auto *TS = make<ThunkSection>(OS, Off);
  ThunkSections[ISR].push_back(TS);
  return TS;
}

std::pair<Thunk *, bool> ThunkCreator::getThunk(SymbolBody &Body,
                                                uint32_t Type) {
  auto Res = ThunkedSymbols.insert({&Body, std::vector<Thunk *>()});
  if (!Res.second) {
    // Check existing Thunks for Body to see if they can be reused
    for (Thunk *ET : Res.first->second)
      if (ET->isCompatibleWith(Type))
        return std::make_pair(ET, false);
  }
  // No existing compatible Thunk in range, create a new one
  Thunk *T = addThunk(Type, Body);
  Res.first->second.push_back(T);
  return std::make_pair(T, true);
}

// Call Fn on every executable InputSection accessed via the linker script
// InputSectionDescription::Sections.
void ThunkCreator::forEachExecInputSection(
    ArrayRef<OutputSection *> OutputSections,
    std::function<void(OutputSection *, std::vector<InputSection *> *,
                       InputSection *)>
        Fn) {
  for (OutputSection *OS : OutputSections) {
    if (!(OS->Flags & SHF_ALLOC) || !(OS->Flags & SHF_EXECINSTR))
      continue;
    for (BaseCommand *BC : OS->Commands)
      if (auto *ISD = dyn_cast<InputSectionDescription>(BC)) {
        CurTS = nullptr;
        for (InputSection *IS : ISD->Sections)
          Fn(OS, &ISD->Sections, IS);
      }
  }
}

// Process all relocations from the InputSections that have been assigned
// to OutputSections and redirect through Thunks if needed.
//
// createThunks must be called after scanRelocs has created the Relocations for
// each InputSection. It must be called before the static symbol table is
// finalized. If any Thunks are added to an OutputSection the output section
// offsets of the InputSections will change.
//
// FIXME: All Thunks are assumed to be in range of the relocation. Range
// extension Thunks are not yet supported.
bool ThunkCreator::createThunks(ArrayRef<OutputSection *> OutputSections) {
  if (Pass > 0)
    ThunkSections.clear();

  // Create all the Thunks and insert them into synthetic ThunkSections. The
  // ThunkSections are later inserted back into the OutputSection.

  // We separate the creation of ThunkSections from the insertion of the
  // ThunkSections back into the OutputSection as ThunkSections are not always
  // inserted into the same OutputSection as the caller.
  forEachExecInputSection(OutputSections, [&](OutputSection *OS,
                                              std::vector<InputSection *> *ISR,
                                              InputSection *IS) {
    for (Relocation &Rel : IS->Relocations) {
      SymbolBody &Body = *Rel.Sym;
      if (Thunks.find(&Body) != Thunks.end() ||
          !Target->needsThunk(Rel.Expr, Rel.Type, IS->File, Body))
        continue;
      Thunk *T;
      bool IsNew;
      std::tie(T, IsNew) = getThunk(Body, Rel.Type);
      if (IsNew) {
        // Find or create a ThunkSection for the new Thunk
        ThunkSection *TS;
        if (auto *TIS = T->getTargetInputSection())
          TS = getISThunkSec(TIS);
        else
          TS = getOSThunkSec(OS, ISR);
        TS->addThunk(T);
        Thunks[T->ThunkSym] = T;
      }
      // Redirect relocation to Thunk, we never go via the PLT to a Thunk
      Rel.Sym = T->ThunkSym;
      Rel.Expr = fromPlt(Rel.Expr);
    }
  });
  // Merge all created synthetic ThunkSections back into OutputSection
  mergeThunks();
  ++Pass;
  return !ThunkSections.empty();
}

template void elf::scanRelocations<ELF32LE>(InputSectionBase &);
template void elf::scanRelocations<ELF32BE>(InputSectionBase &);
template void elf::scanRelocations<ELF64LE>(InputSectionBase &);
template void elf::scanRelocations<ELF64BE>(InputSectionBase &);