[ELF] Make section order rely on explicit member

[jhenderson]

Summary

This is an optional prerequisite to D38361. If it is not committed separately, it will be committed as part of that review.

The idea is to remove the dependency on OutSecOff when ordering SHF_LINK_ORDER sections. This is to allow no longer temporarily setting the OutSecOff field via updateOffset.

[peter.smith]

I think that this could be a useful thing to do as it would allow the handling of SHF_LINK_ORDER sections to be moved from its current location in OutputSection::finalize() to just after OutSecPos is determined. This would permit an implementation of .ARM.exidx table deduplication (pr34501) to run without needing an early AssignAddresses.

One possible downside is OutSecPos will only be set for InputSections added via addSection(), ThunkSections and any other late inserted sections won't have this set. This isn't necessarily a problem as inserting sections doesn't change the relative ordering of any existing InputSections, however I think we need to either comment that OutSecPos is not set for inserted sections such as Thunks, or make AssignAddresses update the OutSecPos.

[jhenderson]

Updated comments to make clear that the OutSecPos field is not set for thunk sections. Also made it an Optional type, to better indicate that it might not always be set, and assert if attempting to use for SHF_LINK_ORDER when not set.

[jhenderson]

In D38687#891902, @peter.smith wrote:

One possible downside is OutSecPos will only be set for InputSections added via addSection(), ThunkSections and any other late inserted sections won't have this set. This isn't necessarily a problem as inserting sections doesn't change the relative ordering of any existing InputSections, however I think we need to either comment that OutSecPos is not set for inserted sections such as Thunks, or make AssignAddresses update the OutSecPos.

I think, until there is a concrete use case for this in thunk sections etc. that I prefer not to update this during assignAddresses to keep things simpler. I'm not opposed to that though if it becomes necessary later on.

[peter.smith]

Thanks for the update, I'm happy with that change. No more comments from me.

[jhenderson]

Ping.

@ruiu, please could you let me know whether you want this done separately to D38361.

[ruiu]

Is my understanding correct that if you check in https://reviews.llvm.org/D38687, you don't need this and https://reviews.llvm.org/D38361?

I thought about all these patches carefully, and I'm leaning towards https://reviews.llvm.org/D38687 because it is by far simple, doesn't need a new member in any class, and it is becoming more in line with other code that uses section offsets. Section offsets used to be computed only once, and once they are set, they would never change. The situation quickly changed because of linker scripts and range extension thunks. In particular, in order to implement the range extension, we need to reassign offsets until they converge. So, section offsets are no longer computed-once value in any sense. So, it started feeling more natural to use section offsets than before.

[jhenderson]

In D38687#912500, @ruiu wrote:

Is my understanding correct that if you check in https://reviews.llvm.org/D38687, you don't need this and https://reviews.llvm.org/D38361?

I thought about all these patches carefully, and I'm leaning towards https://reviews.llvm.org/D38687 because it is by far simple, doesn't need a new member in any class, and it is becoming more in line with other code that uses section offsets. Section offsets used to be computed only once, and once they are set, they would never change. The situation quickly changed because of linker scripts and range extension thunks. In particular, in order to implement the range extension, we need to reassign offsets until they converge. So, section offsets are no longer computed-once value in any sense. So, it started feeling more natural to use section offsets than before.

So there are currently 3 related patches up for review, D38321, D38361, and D38687 (this one - I think you may have linked to the wrong review in the above comment, based on what you said). Either D38321 needs committing to fix the issue, or D38361, or D38687 and a stripped down version of D38361.

I've looked again at D38321, and although it is sufficient to fix the problem, it still feels like a sticky plaster covering up the fact that we compute a potentially incorrect section Size and Offset too early, which then causes problems further down the line (note that there is even a comment in the code explaining that this is a crude approximation). D38361 is a more comprehensive fix to this, as it means we have no Size or Offset set until assignAddresses is called (which is correct, because only assignAddresses has all the necessary information needed to calculate these). To me, the converging loop point is a different situation, in my opinion, because the Size and Offset values are always correct immediately after assignAddresses for the ELF as it stands at that point, although sections might later need adding/expanding (e.g. due to thunks), hence the need to rerun assignAddresses.

It's also worth pointing out that the changes for the MIPS GOT dynamic tag in D38361 are needed regardless, since this needs to be set post-thunk creation, and take into account linker script section layout. I should probably spin off a separate patch for that, thinking about it, since I'm pretty sure it's actually a bug even without these other changes - I'll see if I can come up with a test case to illustrate.

I'm concerned that by leaving the potentially incorrect Size and Offset as is, we may cause further confusion and have more code in the future that tries to rely on these values before they are finalized, so my preference is still to go with D38361 (and maybe this one, D38687).

[jhenderson]

Ping

[ruiu]

This patch is included in https://reviews.llvm.org/D38361, so can you abandon this change? On the other hand https://reviews.llvm.org/D38361 includes a MIPS-ness that I've already reviewed. Can you fix that too?

ELF/InputSection.h

public:
   template <class ELFT> void writeTo(uint8_t *Buf);
 
   OutputSection *getParent() const;
 
   // The offset from beginning of the output sections this section was assigned
   // to. The writer sets a value.
   uint64_t OutSecOff = 0;
 
+  // The order in which the section was added to its output section. This is
+  // used when ordering SHF_LINK_ORDER sections. It is not set for sections
+  // inserted late, such as thunk sections.
+  llvm::Optional<size_t> OutSecPos;
+
   static bool classof(const SectionBase *S);
 
   InputSectionBase *getRelocatedSection();
 
   template <class ELFT, class RelTy>
   void relocateNonAlloc(uint8_t *Buf, llvm::ArrayRef<RelTy> Rels);
 
   // Used by ICF.

ELF/OutputSections.h

public:
   template <class ELFT> void finalize();
   template <class ELFT> void writeTo(uint8_t *Buf);
   template <class ELFT> void maybeCompress();
   uint32_t getFiller();
 
   void sort(std::function<int(InputSectionBase *S)> Order);
   void sortInitFini();
   void sortCtorsDtors();
+
+private:
+  // The number of input sections assigned to this section excluding
+  // late-inserted sections, such as thunk sections.
+  size_t InputSectionCount = 0;
 };
 
 int getPriority(StringRef S);
 
 // All output sections that are handled by the linker specially are
 // globally accessible. Writer initializes them, so don't use them
 // until Writer is initialized.
 struct Out {

ELF/OutputSections.cpp

static uint64_t updateOffset(uint64_t Off, InputSection *S) {
   return Off + S->getSize();
 }
 
 void OutputSection::addSection(InputSection *S) {
   assert(S->Live);
   Live = true;
   S->Parent = this;
   this->updateAlignment(S->Alignment);
+  S->OutSecPos = InputSectionCount++;
 
   // The actual offsets will be computed by assignAddresses. For now, use
   // crude approximation so that it is at least easy for other code to know the
   // section order. It is also used to calculate the output section size early
   // for compressed debug sections.
   this->Size = updateOffset(Size, S);
 
   // If this section contains a table of fixed-size entries, sh_entsize
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;
+  assert(LA->OutSecPos && LB->OutSecPos &&
+         "Cannot compare late-inserted section positions.");
+  return LA->OutSecPos < LB->OutSecPos;
 }
 
 template <class ELFT>
 static void finalizeShtGroup(OutputSection *OS,
                              ArrayRef<InputSection *> Sections) {
   assert(Config->Relocatable && Sections.size() == 1);
 
   // sh_link field for SHT_GROUP sections should contain the section index of