[ELF] Stop setting output section size early

[jhenderson]

Summary

This is an alternative to D38321. The motivation, as described in that patch, is the same:

The size of an OutputSection is calculated early, to aid handling of compressed debug sections. However, subsequent to this point, unused synthetic sections are removed. In the event that an OutputSection, from which such an InputSection is removed, is still required (e.g. because it has a symbol assignment), and no longer has any InputSections, dot assignments, or BYTE()-family directives, the size member is never updated when processing the commands. If the removed InputSection had a non-zero size (such as a .got.plt section), the section ends up with the wrong size in the output.

In this version, I have stopped estimating the value of the OutputSection Size and InputSection OutSecOff members early. There were a couple of issues I had to resolve, as part of this change:

1. Compressed debug sections still need the Size set early, because they are not processed in assignAddresses. The original behaviour of setting the size early is maintained for such sections.
2. The order of input sections is important for SHF_LINK_ORDER sections. This was previously relying on OutSecOff being an approximation for determining the final order. By making OutSecOff and OutputSection Size clearly not be the offset and size respectively, and instead making them represent indexes and section count, it should be much harder to misuse them.

[jhenderson]

Ping

[ruiu]

This is much more complicated than https://reviews.llvm.org/D38321, but I wonder if it has to be. I feel like this part of code is becoming out of control.

Speaking of this patch, why don't you assign offsets in maybeCompress?

ELF/SyntheticSections.cpp

844–848 ↗

(On Diff #116981)

What happens when a user starts modifying the output using the linker script?

[jhenderson]

Moved offset and size calculation of compressed debug sections into maybeCompress as suggested. I have not got a setup that is able to run the corresponding tests, because it requires zlib (I tried installing it on my linux copy of LLVM and it still didn't work). If anybody is able to run these tests, I'd much appreciate it.

[jhenderson]

In D38361#890146, @ruiu wrote:

This is much more complicated than https://reviews.llvm.org/D38321, but I wonder if it has to be. I feel like this part of code is becoming out of control.

Are you referring to the MipsGot stuff, or the addSection code? I feel like this change makes the addSection code more correct, if anything, as it stops setting a "false" value for OutputSection::Size.

ELF/SyntheticSections.cpp

844–848 ↗

(On Diff #116981)

The output section sizes will be different to what is estimated here, meaning that the number of GOT entries may not be entirely correct. I think that the only way around this is if we properly loop over assignAddresses until the sizes are all stable. This is an existing issue with the current behaviour anyway, and I see that @peter.smith already mentioned this in D29983#681632:

In the general case we will need to assign addresses multiple times as it is possible to write linker scripts where adding thunks causes address expressions in the script to change in ways that breaks the address calculations.

The size calculation for the GOT relies on the size calculated by assignAddresses, but that is not final until after thunk creation. As things stand, I think the code is slightly broken anyway, but I think it might be fixable by calling assignAddresses again immediately before the updateAllocSize call. I will look a that shortly.

[peter.smith]

Apologies for the drive by comment, I need to leave the office fairly soon. In this specific case might it be simpler to only early calculate the size of non SHF_ALLOC content such as debug sections as the OutputSection doesn't get an address, just an offset and doesn't affect the addresses of any other SHF_ALLOC content, it is therefore safe to calculate the OutputSection size early.

In the general case I think the late addition and removal of content such as Thunks, Mips GOT entries, errata fixes and I'm guessing at RiscV relaxation are going to require some kind of iteration to a fixed point. I usually find iterating to a fixed point better than trying to predict addresses/sizes as it is easy to miss hard to predict corner cases. I'm wondering if it is possible to make this kind of iteration clearer by having a kind of Relaxation() stage that we can add functions that may need to update addresses and sizes to, this should hopefully make such code easier to understand. Probably a separate series of refactorings though.

I recommend splitting out the SHF_LINK_ORDER change into a separate patch if it is unrelated.

[jhenderson]

In D38361#890717, @peter.smith wrote:

Apologies for the drive by comment, I need to leave the office fairly soon. In this specific case might it be simpler to only early calculate the size of non SHF_ALLOC content such as debug sections as the OutputSection doesn't get an address, just an offset and doesn't affect the addresses of any other SHF_ALLOC content, it is therefore safe to calculate the OutputSection size early.

Unfortunately, it isn't safe: non-alloc sections can still be manipulated in linker scripts. For example, you could do something like .foobar : { *(.foo); . += 16; *(.bar) } in your script, which leaves a 16-byte gap in the output section, whose size is not accounted for in the early calculation, and is only later fixed by assignAddresses. This isn't an issue for compressed debug sections, because we explicitly ignore custom layout in scripts for such sections.

In the general case I think the late addition and removal of content such as Thunks, Mips GOT entries, errata fixes and I'm guessing at RiscV relaxation are going to require some kind of iteration to a fixed point. I usually find iterating to a fixed point better than trying to predict addresses/sizes as it is easy to miss hard to predict corner cases. I'm wondering if it is possible to make this kind of iteration clearer by having a kind of Relaxation() stage that we can add functions that may need to update addresses and sizes to, this should hopefully make such code easier to understand. Probably a separate series of refactorings though.

I completely agree with this general idea, although "Relaxation" is another term that is getting a bit too over-loaded for my taste (like "finalize"), so I'd call it something else.

I recommend splitting out the SHF_LINK_ORDER change into a separate patch if it is unrelated.

It's not entirely unrelated, but it could be a separate prerequisite patch. I'll look at splitting it off.

[jhenderson]

In D38361#891842, @jhenderson wrote:

In D38361#890717, @peter.smith wrote:

I recommend splitting out the SHF_LINK_ORDER change into a separate patch if it is unrelated.

It's not entirely unrelated, but it could be a separate prerequisite patch. I'll look at splitting it off.

I've created D38687 for this. It could be a standalone change, but the motivation is less important in that situation. @ruiu, if you prefer that I do it as part of this change directly, I'm happy to do so.

I'm going to leave the corresponding changes in this diff, unless the other review is committed.

[jhenderson]

ELF/SyntheticSections.cpp

844–848 ↗

(On Diff #116981)

Whilst attempting to avoid this estimating by calling assignAddresses again, I found another issue, which is also theoretically present prior to my changes: the DT_MIPS_LOCAL_GOTNO depends on the number of local got entries, but these are dependent on the size calculated in updateAllocSize(). Updating this size, e.g. due to additional thunks being created, might render the the dynamic tag value invalid.

[peter.smith]

Whilst attempting to avoid this estimating by calling assignAddresses again, I found another issue, which is also theoretically present prior to my changes: the DT_MIPS_LOCAL_GOTNO depends on the number of local got entries, but these are dependent on the size calculated in updateAllocSize(). Updating this size, e.g. due to additional thunks being created, might render the the dynamic tag value invalid.

My apologies for missing that at the time, unfortunately I'm not too familiar with the Mips ABI. It looks like it could be fixed by implementing DynamicSection::postThunkContents() and updating the value of DT_MIPS_LOCAL_GOTNO. Luckily this won't change the size of the .dynamic section so it can be delayed.

[jhenderson]

1. Reworked when assignAddresses and applySynthetic are called with regards to the MIPS GOT section, so that it has access to the right variables. This allows me to get rid of the estimating of sizes, so is more correct.
2. Delayed setting the DT_MIPS_LOCAL_GOTNO tag until a new postThunkContents for DynamicSection (thanks for the suggestion @peter.smith).
3. Removed unnecessary references to string table sections when calling postThunkContents, since they do not implement this function.
4. Removed the finalizeContents implementation for MIPS GOT since it does not do anything useful any more (previously it only called updateAllocSize, but too early to be useful).
5. Updated the SHF_LINK_ORDER-related changes that are in the latest version of D38687.
6. Fixed the line breaks in a comment in the area I was changing.

[ruiu]

ELF/SyntheticSections.cpp

1162–1164 ↗

(On Diff #118217)

Add blank lines before and after this so that it is clear which code this comment is talking about.

1180 ↗

(On Diff #118217)

Is there any way other than backfilling DT_MIPS_LOCAL_GOTNO?

For example, .eh_frame_hdr depends on .eh_frame, and that dependency is handled simply by calling .eh_frame's writeTo before .eh_frame_hdr's writeTo. Unless there is a circular dependency, you don't need to backfill a value.

[jhenderson]

ELF/SyntheticSections.cpp

1180 ↗

(On Diff #118217)

You're right, there isn't actually a circular dependency here. We can set the value during writeTo. There is an alternative option - move the adding of the tag (and the DT_NULL tag) into postThunkContents (or optionally all tags), since I don't think there's any dependency on the dynamic section size in thunk creation or the MIPS GOT creation.

[jhenderson]

Rebased and addressed review comments:

1. Add blank lines around comment/code block.
2. Revert addition of postThunkContents for dynamic sections and instead assign the value for DT_MIPS_LOCAL_GOTNO during DynamicSection::writeTo.

[jhenderson]

Rebased following landing of range-based thunks. This allowed me to remove the additional passes I had added to get the addresses right in updateAllocSize for the MIPS GOT section.

[jhenderson]

• Removed changes to do with DT_MIPS_LOCAL_GOTNO. These are present in D39493, which must land first (otherwise this change breaks the MIPS GOT tests).
• Removed removal of MipsGot->finalizeContents(). This function is unnecessary, but harmless, so to make this diff simpler, I'm removing it for now. A later change could remove it if desired.

[jhenderson]

I was re-verifying this patch, prior to a ping, but I discovered that when applied, it highlighted a problem with rLLD318924, resulting in test failures with this patch. The problem is that that commit is another example of code relying on the section Size before it is finalized (and getting it wrong for some linker scripts cases). I have filed https://bugs.llvm.org/show_bug.cgi?id=35478 for it.

This made me wonder whether changing Size and OutSecOff to llvm::Optional type would bring some benefits. It would ensure that people cannot use the fields before they have been set for the first time (which with this patch would be in the first call to assignAddresses). The downside is the need to dereference it everywhere where it is used, so could cause quite a bit of code churn. Also, presumably tests would pick up any misuse after this point, so it might not be all that useful. Thoughts?

[peter.smith]

My apologies for PR35478, I'll take a look this afternoon. The main intention there was to guard against 0 sized SyntheticSections as the user can't always be held responsible for them. Personally I'd be in favour of making those fields optional as I clearly didn't have enough tests to catch the problem there. I also think that our tests, for good reasons, tend to look at one feature at a time and we miss out on cases where combinations of features cause problems.

[peter.smith]

I think that this should now be unblocked after the reverting the change that caused PR35478. I'd very much like to see this land as I'd like to implement ARM.exidx table compression and that will depend on the OutSecPos changes here.

[jhenderson]

@rafael wrote:
I don't like the idea of adding a member for the section position. At no point we need the position and the offset simultaneously and having both variables means they can get inconsistent.

As far as I'm aware there is no case where the two could get inconsistent, once set - that would require the ability to reorder the sections in the output section.

One way to look at the current issue is that the early estimate of the offset is correct in the common case, which makes it really easy to use it incorrectly before the final value is computed.

I agree that using a value that is very different is likely to be spotted, although it's not guaranteed to be (especially if working with only a single InputSection in an output section).

If we make the value almost always wrong, that problem goes away. What do you think of the attached patch? We could rename OutSecOff to OutSecOffsetOrIndex, but that doesn't seem worth it.

Given that both you and @ruiu seem reluctant to have new members, I've tentatively adopted it with a few changes and additions to the comments. I don't like using a member for two different purposes still, even if those two purposes don't overlap in time, but I'd rather get this change in in at least some form. Could you let me know what you think of the diff with the comment changes, please. In particular, I've moved the comments relating to the Size and OutSecOff members to make their dual purpose clear at their point of definition, and I've not added the suggested additional comments to maybeCompress - they're unnecessary as we already have a comment in assignOffsets saying that we don't support custom layout for compressed debug sections.

I'm wondering if it is feasible to check and disable compression if a non input section description command is detected in the debug section being compressed?

It should be possible to at least produce an error message.

I'd support something like that (it should be easy to add to the loop I'm adding in maybeCompress), but not as part of this change.

[peter.smith]

No objections from me. I've successfully rebased D40964 onto this change.

ELF/InputSection.h

InputSection(ObjFile<ELFT> *F, const typename ELFT::Shdr *Header,
                StringRef Name);
 
   // Write this section to a mmap'ed file, assuming Buf is pointing to
   // beginning of the output section.
   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;
-
-  static bool classof(const SectionBase *S);
-
-  InputSectionBase *getRelocatedSection();
+  // This variable has two usages. Initially, it represents an index in the
+  // OutputSection's InputSection list, and is used when ordering SHF_LINK_ORDER
+  // sections. After assignAddresses is called, it represents the offset from
+  // the beginning of the output section this section was assigned to.
+  uint64_t OutSecOff = 0;
+
+  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.
   uint32_t Class[2] = {0, 0};
 
   // Called by ICF to merge two input sections.

ELF/LinkerScript.cpp

void LinkerScript::assignOffsets(OutputSection *Sec) {
 
   switchTo(Sec);
 
   // We do not support custom layout for compressed debug sectons.
   // At this point we already know their size and have compressed content.
   if (Ctx->OutSec->Flags & SHF_COMPRESSED)
     return;
 
+  // The Size previously denoted how many InputSections had been added to this
+  // section, and was used for sorting SHF_LINK_ORDER sections. Reset it to
+  // compute the actual size value.
+  Sec->Size = 0;
+
   // We visited SectionsCommands from processSectionCommands to
   // layout sections. Now, we visit SectionsCommands again to fix
   // section offsets.
   for (BaseCommand *Base : Sec->SectionCommands) {
     // This handles the assignments to symbol or to the dot.
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
       assignSymbol(Cmd, true);
       continue;

ELF/OutputSections.h

public:
   // section in PT_LOAD.
   PhdrEntry *PtLoad = nullptr;
 
   // Pointer to a relocation section for this section. Usually nullptr because
   // we consume relocations, but if --emit-relocs is specified (which is rare),
   // it may have a non-null value.
   OutputSection *RelocationSection = nullptr;
 
-  // The following fields correspond to Elf_Shdr members.
+  // Initially this field is the number of InputSections that have been added to
+  // the OutputSection so far. Later on, after a call to assignAddresses, it
+  // corresponds to the Elf_Shdr member.
   uint64_t Size = 0;
+
+  // The following fields correspond to Elf_Shdr members.
   uint64_t Offset = 0;
   uint64_t LMAOffset = 0;
   uint64_t Addr = 0;
   uint32_t ShName = 0;
 
   void addSection(InputSection *IS);
 
   // Location in the output buffer.
public:
   template <class ELFT> void maybeCompress();
 
   void sort(std::function<int(InputSectionBase *S)> Order);
   void sortInitFini();
   void sortCtorsDtors();
 
 private:
   // Used for implementation of --compress-debug-sections option.
-  std::vector<uint8_t> ZDebugHeader;
-  llvm::SmallVector<char, 1> CompressedData;
-
-  uint32_t getFiller();
-};
-
+  std::vector<uint8_t> ZDebugHeader;
+  llvm::SmallVector<char, 1> CompressedData;
+
+  uint32_t getFiller();
+};
+
 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 {
   static uint8_t First;
   static OutputSection *Opd;

ELF/OutputSections.cpp

if (Type != IS->Type) {
               getELFSectionTypeName(Config->EMachine, Type));
       Type = SHT_PROGBITS;
     }
   }
 
   IS->Parent = this;
   Flags |= IS->Flags;
   Alignment = std::max(Alignment, IS->Alignment);
-
-  // 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.
-  IS->OutSecOff = alignTo(Size, IS->Alignment);
-  this->Size = IS->OutSecOff + IS->getSize();
+  IS->OutSecOff = Size++;
 
   // If this section contains a table of fixed-size entries, sh_entsize
   // holds the element size. If it contains elements of different size we
   // set sh_entsize to 0.
   if (Entsize != IS->Entsize)
     Entsize = 0;
 
   if (!IS->Assigned) {

 template <class ELFT> void OutputSection::maybeCompress() {
   typedef typename ELFT::Chdr Elf_Chdr;
 
   // Compress only DWARF debug sections.
   if (!Config->CompressDebugSections || (Flags & SHF_ALLOC) ||
       !Name.startswith(".debug_"))
     return;
 
+  // Calculate the section offsets and size pre-compression.
+  Size = 0;
+  for (BaseCommand *Cmd : SectionCommands)
+    if (auto *ISD = dyn_cast<InputSectionDescription>(Cmd))
+      for (InputSection *IS : ISD->Sections) {
+        IS->OutSecOff = alignTo(Size, IS->Alignment);
+        this->Size = IS->OutSecOff + IS->getSize();
+      }
+
   // Create a section header.
   ZDebugHeader.resize(sizeof(Elf_Chdr));
   auto *Hdr = reinterpret_cast<Elf_Chdr *>(ZDebugHeader.data());
   Hdr->ch_type = ELFCOMPRESS_ZLIB;
   Hdr->ch_size = Size;
   Hdr->ch_addralign = Alignment;
 
   // Write section contents to a temporary buffer and compress it.

test/ELF/linkerscript/unused-synthetic.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
 # RUN: echo "SECTIONS { \
 # RUN:    .got  : { *(.got) } \
 # RUN:    .plt  : { *(.plt) } \
 # RUN:    .text : { *(.text) } \
 # RUN:  }" > %t.script
 # RUN: ld.lld -shared -o %t.so --script %t.script %t.o
 
 # RUN: llvm-objdump -section-headers %t.so | FileCheck %s
 # CHECK-NOT:  .got
 # CHECK-NOT:  .plt
 # CHECK:      .text
 # CHECK-NEXT: .dynsym
 
+# Test that the size of a removed unused synthetic input section is not added
+# to the output section size. Adding a symbol assignment prevents removal of
+# the output section, but does not cause the section size to be recomputed.
+# RUN: echo "SECTIONS { \
+# RUN:    .got.plt : { a_sym = .; *(.got.plt) } \
+# RUN:  }" > %t2.script
+# RUN: ld.lld -shared -o %t2.so --script %t2.script %t.o
+# RUN: llvm-objdump -section-headers %t2.so | FileCheck %s --check-prefix=CHECK2
+# CHECK2: .got.plt 00000000
+
 .global _start
 _start:
   nop