[ELF2] PPC64 needs to delay local-call relocations until after the function-descriptor values are known

[hfinkel]

Summary

I've separated this into a separate patch because it brings up a design question (which we might wish to solve as I've done here, or we might wish to solve in a completely different way).

Under PPC64 ELF v1 ABI, the symbols associated with each function name don't point directly to the code in the .text section (or similar), but rather to a function descriptor structure in a special data section named .opd. The elements in the .opd structure include a pointer to the actual code, and a the relevant TOC base value. Both of these are themselves set by relocations.

When we have a local call, we need the relevant relocation to refer directly to the target code, not to the function-descriptor in the .opd section. Only when we have a .plt stub do we care about the address of the .opd function descriptor itself.

We don't process relocations for the .opd section until after we process the code sections, and so when we're processing the relocation for a local call, we don't yet know the address of that call. We know the address of its function descriptor, but won't know the value in the descriptor until after we process relocations for the .opd section.

Here we store a vector of lambda function for each function descriptor, allowing us to go back and process the call relocations for local functions once the function-descriptor values are known.

Obviously still missing test cases, but feedback is certainly appreciated.

With this patch (and the others posted today), I can link, and run, a dynamically-compiled "hello world" application on big-Endian PPC64/Linux (ELF v1 ABI) using lld.

[ruiu]

If my understanding is correct, the problem is that when we apply relocations, relocations in .opd may not have been applied yes, so you have to backfill relocations that refer function descriptors in .opd.

If so, it seems to me that you can solve the problem by applying all relocations in .opd first and then rest,. Doesn't this work?

[hfinkel]

In D13566#263240, @ruiu wrote:

If my understanding is correct, the problem is that when we apply relocations, relocations in .opd may not have been applied yes, so you have to backfill relocations that refer function descriptors in .opd.

If so, it seems to me that you can solve the problem by applying all relocations in .opd first and then rest,. Doesn't this work?

Yes, if we always applied relocations in .opd first, then we'd be able to save and use that information later for the relocations in the text sections.

Should we add some kind of target hook that allows it to somehow adjust the order in which the relocations are applied? Does this require separating that process from the order in which the sections are written? In short, how would you like this to work?

[hfinkel]

Updated based on reviewer comments (and some IRC discussion), and added a test case.

[ruiu]

Writer<ELFT>::writeSections() {

ELF/Target.cpp

435–441

You may be able to eliminate the hash table by reading back previous relocatino results for R_PPC64_ADDR64 from Buf.

if (!ForPltEntry)
  R = read64be(Buf + R - BaseAddr);

ELF/Target.h

96 ↗

(On Diff #37132)

Mutable memebers are not generally good, so I'd avoid using that.

ELF/Writer.cpp

654–664 ↗

(On Diff #37132)

Changing the order of the vector could have significant impact because that's not supposed to happen. Please do like this

for (OutputSectionBase<ELFT::Is64Bits> *Sec : OutputSections)
  if (Sec->getName() == ".opd")
    Sec->writeTo(Buf + Sec->getFileOff();
for (OutputSectionBase<ELFT::Is64Bits> *Sec : OutputSections)
  if (Sec->getName() != ".opd")
    Sec->writeTo(Buf + Sec->getFileOff();

[hfinkel]

ELF/Target.cpp

435–441

Two problems:

1. The relocated addresses are in a different section (and, thus, I assume, have a different base buffer pointer)
2. If the relocation is not pointing to a function descriptor (which it might not), then we need to keep the original symbol address.

An alternative would be to be able to explicitly get the .opd section, do a bounds check (just as I do for the .plt section), and then read from its buffer. Is there a good way to do that?

ELF/Target.h

96 ↗

(On Diff #37132)

The alternative is to make relocateOne non-const. Is that okay? [no need to answer this question if we don't need the map at all, as per the thread below].

[ruiu]

ELF/Target.cpp

435–441

Ah, you are right. But how about keeping a pointer to .opd section? If you have a pointer to .opd section, can you get the value you want from the section contents?

[hfinkel]

Updated to reflect reviewer comments (and some discussion on IRC).

[ruiu]

ELF/OutputSections.cpp

43–50 ↗

(On Diff #37141)

Please rebase to head.

ELF/OutputSections.h

290–291 ↗

(On Diff #37141)

Alright, I found that not look very good. How about adding these two fields to PPC64TargetInfo?

[hfinkel]

ELF/OutputSections.h

290–291 ↗

(On Diff #37141)

I'll try that.

FYI: PPC64, Itanium and HPPA seem to use the .opd section. Thus, while theoretically generic, I suspect we can consider this to be PPC64-specific in practice.

[hfinkel]

ELF/OutputSections.h

290–291 ↗

(On Diff #37141)

Alright, this can certainly be done. The largest issue is that the type of the output section depends on the target's object type, and we cannot universally stash the pointer to the section away in PPC64 target info without some form of type erasure and/or dispatch to the target.

I'll upload a pure rebase of this patch, and then a version where I've moved the data members into PPC64TargetInfo (but using a void* to get around the aforementioned issue).

[hfinkel]

Rebased to trunk.

[hfinkel]

Uploading the full-context patch.

[hfinkel]

Move the .opd section and buffer pointers into PPC64TargetInfo. Because the type of the section object depends on ELFT, I've made the type of pointer in PPC64TargetInfo a void* so that we can universally stash the pointer value there.

[ruiu]

ELF/Target.cpp

448

read64be(OpdBuf + S + A - OpdStart);

ELF/Target.h

90–91 ↗

(On Diff #37182)

No need to make them static. They can be non-static members.

Because PPC64 is ELF64BE, you can use the strict type.

OutputSection<ELF64BE> *OpdPtr = nullptr;
static uint8_t *OpdBuf = nullptr;

ELF/Writer.cpp

479–480 ↗

(On Diff #37182)

if (OutputSection<ELFT> *Sec = Map.lookup({".opd", ...))
  Target->Opd = reinterpret_cast<OutputSection<ELF64BE> *>(Sec);

[hfinkel]

ELF/Writer.cpp

479–480 ↗

(On Diff #37182)

Do you want me to move Opd and OpdBuf into TargetInfo to make this work?

[ruiu]

ELF/Writer.cpp

479–480 ↗

(On Diff #37182)

Ah, then this?

if (OutputSection<ELFT> *Sec = Map.lookup({".opd", ...))
  reinterpet_cast<PPC64TargetInfo *>(Target)->Opd = reinterpret_cast<OutputSection<ELF64BE> *>(Sec);

[hfinkel]

ELF/Writer.cpp

479–480 ↗

(On Diff #37182)

No, because they any object file with a section names .opd, that happens not to be targeting ppc64, will cause us to corrupt our internal data structures. This does not seem all that far fetched to me, because when we also add support for little-endian ppc64 (power8 and later), that target will not use .opd, but I can certainly imagine some tools still producing .opd sections.

To think ahead a little bit, can I add a Target callback to enable it to inspect the Map (or maybe just the OutputSections array)? The target needs to grab .opd to do this function-descriptor indirection, but that's not the end of this. We'll also want to grab .toc and .tocbss to really get the TOC base address calculation right. We'll want .branch_lt (which we'll need to add if not already present) in order to generate long-branch stubs.

[ruiu]

ELF/Writer.cpp

479–480 ↗

(On Diff #37182)

I'm not confident if we really want to have that function. That might be useful, but can be a bit overkill. I'd just add Opd and OpdBuf (but I'd name OpdStart instead of OpdBuf) to Out for now, which is the previous code. Sorry for back-and-force.

[hfinkel]

ELF/Writer.cpp

479–480 ↗

(On Diff #37182)

Not a problem.

Why OpdStart? I think that could be confused with the starting virtual address. Would OpdData be better?

[ruiu]

ELF/Writer.cpp

479–480 ↗

(On Diff #37182)

Mainly because Bigcheese is going to use Start prefix. But I don't have a strong preference. OK in either way.

[hfinkel]

r250122, thanks!

ELF/Target.cpp

 //===- Target.cpp ---------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Target.h"
 #include "Error.h"
 #include "OutputSections.h"
 #include "Symbols.h"
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/Object/ELF.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/ELF.h"
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 using namespace llvm::ELF;
bool PPC64TargetInfo::isRelRelative(uint32_t Type) const {
   case R_PPC64_REL32:
     return true;
   }
 }
 void PPC64TargetInfo::relocateOne(uint8_t *Buf, uint8_t *BufEnd,
                                   const void *RelP, uint32_t Type,
                                   uint64_t BaseAddr, uint64_t SymVA,
                                   uint64_t GotVA, bool ForPltEntry) const {
+  static DenseMap<uint64_t, std::vector<std::function<void(uint64_t)>>> DelayedRelocs;
+
   typedef ELFFile<ELF64BE>::Elf_Rela Elf_Rela;
   auto &Rel = *reinterpret_cast<const Elf_Rela *>(RelP);
   int64_t Addend = Rel.r_addend;
 
   // The TOC consists of sections .got, .toc, .tocbss, .plt in that
   // order. The TOC starts where the first of these sections starts.
 
   // FIXME: This obviously does not do the right thing when there is no .got
void PPC64TargetInfo::relocateOne(uint8_t *Buf, uint8_t *BufEnd,
   } break;
   case R_PPC64_ADDR32: {
     int32_t Result = static_cast<int32_t>(SymVA + Addend);
     if (SignExtend32<32>(Result) != Result)
       error("Relocation R_PPC64_ADDR32 overflow");
     write32be(Loc, Result);
   } break;
   case R_PPC64_REL24: {
+    auto ApplyReloc = [=](uint64_t SymVAPlusAddend) {
       uint64_t FinalAddress = (BaseAddr + Offset);
-    int32_t delta = static_cast<int32_t>(SymVA - FinalAddress + Addend);
+      int32_t delta = static_cast<int32_t>(SymVAPlusAddend - FinalAddress);
       uint32_t Mask = 0x03FFFFFC;
       if (SignExtend32<24>(delta) != delta)
         error("Relocation R_PPC64_REL24 overflow");
       write32be(Loc, (read32be(Loc) & ~Mask) | (delta & Mask));
 
       if (ForPltEntry && Loc + 8 < BufEnd &&
           read32be(Loc + 4) == 0x60000000 /* nop */)
         write32be(Loc + 4, 0xe8410028); // ld r2,40(r1)
+    };
+
+    if (ForPltEntry) {
+      ApplyReloc(SymVA + Addend);
+    } else {
+      // This is a branch to a local symbol, but we cannot yet resolve it. The
+      // address provided here is that of the function's descriptor in the .opd
+      // section. We need to branch, however, to the address that will appear in
+      // the .opd section, but we won't know what that is until we process
+      // relocations in that section.
+      DelayedRelocs[SymVA + Addend].push_back(ApplyReloc);
+    }
   } break;
   case R_PPC64_REL32: {
     uint64_t FinalAddress = (BaseAddr + Offset);
     int32_t delta = static_cast<int32_t>(SymVA - FinalAddress + Addend);
     if (SignExtend32<32>(delta) != delta)
       error("Relocation R_PPC64_REL32 overflow");
     write32be(Loc, delta);
   } break;
   case R_PPC64_REL64: {
     uint64_t FinalAddress = (BaseAddr + Offset);
     uint64_t Delta = SymVA - FinalAddress + Addend;
     write64be(Loc, Delta);
   } break;
-  case R_PPC64_ADDR64:
+  case R_PPC64_ADDR64: {
     write64be(Loc, SymVA + Addend);
-    break;
+
+    // We might be processing the relocation for a function descriptor, and if
+    // so, we can now go back and fill in this value for local call sites as
+    // well.
+    auto DRI = DelayedRelocs.find(BaseAddr + Offset);
+    if (DRI != DelayedRelocs.end())
+      for (auto &DR : DRI->second)
+        DR(SymVA + Addend);
+  } break;
   default:
     error(Twine("unrecognized reloc ") + Twine(Type));
     break;
   }
 }
 
 PPCTargetInfo::PPCTargetInfo() {
   // PCRelReloc = FIXME