[ELF] Better resemble GNU ld when placing orphan sections into memory regions

[ikudrin]

Summary

An orphan section should be placed in the same memory region as its anchor section if the latter specifies the memory region explicitly. Otherwise, the memory region for an orphan section should be selected by matching section flags and memory region attributes.

[peter.smith]

I'm out of office this week. Will take a look next week if no-one else has.

[MaskRay]

This makes sense to me, but worth a look from Peter.

lld/test/ELF/linkerscript/orphan-memory.test

12

Tabular output from llvm-readelf may be more readonable. WDYT

39

Add a non-SHF_ALLOC orphan section to show that it does not belong to DATA

[ikudrin]

• llvm-readobj -> llvm-readelf
• Added section .nonalloc in the test

lld/test/ELF/linkerscript/orphan-memory.test

12

Not sure because it requires leading zeroes and some regexes, but it is also more compact.

[peter.smith]

lld/ELF/LinkerScript.cpp

909

My first reaction is that I'd expect this to be below the // See if a region can be found by matching section flags.

Looking at LD https://sourceware.org/binutils/docs/ld/MEMORY.html

The attr string is an optional list of attributes that specify whether to use a particular memory region for an input section which is not explicitly mapped in the linker script. As described in SECTIONS, if you do not specify an output section for some input section, the linker will create an output section with the same name as the input section. If you define region attributes, the linker will use them to select the memory region for the output section that it creates.

That implies that if there are attributes/flags for the memory region then we should try these first to make sure that we respect RO, RW etc. If the MEMORY region doesn't have flags then we could fall back on prev in that case. Apologies if I've missed something obvious.

lld/test/ELF/linkerscript/orphan-memory.test

39

Would be good to add a test with attributes (https://sourceware.org/binutils/docs/ld/MEMORY.html) for the memory region as well to make sure that these are respected.

[ikudrin]

lld/ELF/LinkerScript.cpp

909

It looks like their implementation does not fully follow that rule. If the script in the test is changed like this:

MEMORY
{
  TEXT (rwx) : ORIGIN = 0x8000, LENGTH = 0x1000
  DATA (rwx) : ORIGIN = 0x9000, LENGTH = 0x1000
}
...

GNU ld still puts .init_array into DATA, not TEXT.

[ikudrin]

• Add a test with attributes for memory regions

[peter.smith]

I had a play around with ld.bfd and found it really hard to get anything like what I'd expect to work. I had the best luck when using ! due to the loose way the sections match and no direct assignment to memory regions.

Could you try something like this:

.section .text.01, "ax", %progbits
 nop

 .section .rodata.01, "a", %progbits
 .word 10

 .section .init_array,"aw",@init_array
 .zero 0x10

With

MEMORY
{
  TEXT (RX) : ORIGIN = 0x8000, LENGTH = 0x1000
  DATA (W!X) : ORIGIN = 0x9000, LENGTH = 0x1000
}

SECTIONS {
  .text : { *(.text.01) }
}

In this case I get the map file:

Memory Configuration

Name             Origin             Length             Attributes
TEXT             0x0000000000008000 0x0000000000001000 xr
DATA             0x0000000000009000 0x0000000000001000 w !x
*default*        0x0000000000000000 0xffffffffffffffff

Linker script and memory map

LOAD ld.o

.text           0x0000000000008000        0x4
 *(.text.01)
 .text.01       0x0000000000008000        0x4 ld.o
 .text          0x0000000000008004        0x0 ld.o
OUTPUT(a.out elf64-littleaarch64)
LOAD linker stubs

.rodata.01      0x0000000000008004        0x4
 .rodata.01     0x0000000000008004        0x4 ld.o

.init_array     0x0000000000009000       0x10
 .init_array    0x0000000000009000       0x10 ld.o

With .init_array correctly in the W!X region.

I think that this test case on LLD with the proposed change would put .init_array in TEXT as it would follow .rodata.01 which would be assigned to TEXT? I've not had a chance to build LLD with the patch to check. If I'm right it may be worth checking that the previous region has compatible attributes.

lld/ELF/LinkerScript.cpp

909

I think there is a chance that if the prev has incompatible flags with sec we could assign sec incorrectly. I think that in the majority, perhaps all real programs we'll be saved by the sorting order so this won't happen. I think that there is a possible corner case (I've put the test in the main comment). If I'm right it would be useful to test that the sec->flags are compatible with prev.

[ikudrin]

Thanks for the samples, @peter.smith!

My current understanding is that GNU ld puts orphan sections into the same memory regions as their anchor sections if the anchor sections are explicitly assigned to memory regions in the linker script. In that case, it ignores attributes and does the said assignment even if properties of sections and regions conflict. On the other hand, if the anchor section does not have the explicit association and its memory region is selected based on attributes, GNU ld does the same for corresponding orphan sections. That is what your example has demonstrated.

I have updated the patch to support these newly discovered cases. Unfortunately, your sample cannot be used as is in lld right now because the linker ignores the r attribute and thus is unable to put .rodata.01 into the correct region. I am going to prepare another patch to fix that.

[peter.smith]

OK, thanks for the update, I've no further comments. I've set accepted, but please wait to see if MaskRay has any further comments.

[MaskRay]

Worth mentioning that previous error: no memory region specified for section may be accepted like GNU ld now.

lld/ELF/LinkerScript.cpp

894

ditto below

906

lld/ELF/LinkerScript.h

computeInputSections(const InputSectionDescription *,
                        ArrayRef<InputSectionBase *>);
 
   std::vector<InputSectionBase *> createInputSectionList(OutputSection &cmd);
 
   void discardSynthetic(OutputSection &);
 
   std::vector<size_t> getPhdrIndices(OutputSection *sec);
 
-  MemoryRegion *findMemoryRegion(OutputSection *sec);
+  std::pair<MemoryRegion *, MemoryRegion *>
+  findMemoryRegion(OutputSection *sec, MemoryRegion *hint);
 
   void switchTo(OutputSection *sec);
   uint64_t advance(uint64_t size, unsigned align);
   void output(InputSection *sec);
 
   void assignOffsets(OutputSection *sec);
 
   // Ctx captures the local AddressState and makes it accessible

lld/ELF/LinkerScript.cpp

if (sec->addrExpr && script->hasSectionsCommand) {
     // section alignments.
     ctx->outSec->addr = advance(0, ctx->outSec->alignment);
     expandMemoryRegions(ctx->outSec->addr - pos);
   }
 }
 
 // This function searches for a memory region to place the given output
 // section in. If found, a pointer to the appropriate memory region is
-// returned. Otherwise, a nullptr is returned.
-MemoryRegion *LinkerScript::findMemoryRegion(OutputSection *sec) {
+// returned in the first member of the pair. Otherwise, a nullptr is returned.
+// The second member of the pair is a hint that should be passed to the
+// subsequent call of this method.
+std::pair<MemoryRegion *, MemoryRegion *>
+LinkerScript::findMemoryRegion(OutputSection *sec, MemoryRegion *hint) {
   // If a memory region name was specified in the output section command,
   // then try to find that region first.
   if (!sec->memoryRegionName.empty()) {
     if (MemoryRegion *m = memoryRegions.lookup(sec->memoryRegionName))
-      return m;
+      return {m, m};
     error("memory region '" + sec->memoryRegionName + "' not declared");
-    return nullptr;
+    return {nullptr, nullptr};
   }
 
   // If at least one memory region is defined, all sections must
   // belong to some memory region. Otherwise, we don't need to do
   // anything for memory regions.
   if (memoryRegions.empty())
-    return nullptr;
+    return {nullptr, nullptr};
+
+  // An allocatable orphan section should continue the previous memory region.
+  if (sec->sectionIndex == UINT32_MAX && (sec->flags & SHF_ALLOC) && hint)
+    return {hint, hint};
 
   // See if a region can be found by matching section flags.
   for (auto &pair : memoryRegions) {
     MemoryRegion *m = pair.second;
     if ((m->flags & sec->flags) && (m->negFlags & sec->flags) == 0)
-      return m;
+      return {m, nullptr};
   }
 
   // Otherwise, no suitable region was found.
   if (sec->flags & SHF_ALLOC)
     error("no memory region specified for section '" + sec->name + "'");
-  return nullptr;
+  return {nullptr, nullptr};
 }
 
 static OutputSection *findFirstSection(PhdrEntry *load) {
   for (OutputSection *sec : outputSections)
     if (sec->ptLoad == load)
       return sec;
   return nullptr;
 }
void LinkerScript::adjustSectionsBeforeSorting() {
   // clutter the output.
   // We instead remove trivially empty sections. The bfd linker seems even
   // more aggressive at removing them.
   llvm::erase_if(sectionCommands, [&](BaseCommand *base) { return !base; });
 }
 
 void LinkerScript::adjustSectionsAfterSorting() {
   // Try and find an appropriate memory region to assign offsets in.
+  MemoryRegion *hint = nullptr;
   for (BaseCommand *base : sectionCommands) {
     if (auto *sec = dyn_cast<OutputSection>(base)) {
       if (!sec->lmaRegionName.empty()) {
         if (MemoryRegion *m = memoryRegions.lookup(sec->lmaRegionName))
           sec->lmaRegion = m;
         else
           error("memory region '" + sec->lmaRegionName + "' not declared");
       }
-      sec->memRegion = findMemoryRegion(sec);
+      std::tie(sec->memRegion, hint) = findMemoryRegion(sec, hint);
     }
   }
 
   // If output section command doesn't specify any segments,
   // and we haven't previously assigned any section to segment,
   // then we simply assign section to the very first load segment.
   // Below is an example of such linker script:
   // PHDRS { seg PT_LOAD; }

lld/ELF/Writer.cpp

if (i == e)
     return e;
   auto foundSec = dyn_cast<OutputSection>(*i);
   if (!foundSec)
     return e;
 
   // Consider all existing sections with the same proximity.
   int proximity = getRankProximity(sec, *i);
   unsigned sortRank = sec->sortRank;
-  if (script->hasPhdrsCommands())
-    // Prevent the orphan section to be placed before the found section because
-    // that can result in adding it to a previous segment and changing flags of
-    // that segment, for example, making a read-only segment writable.
+  if (script->hasPhdrsCommands() || !script->memoryRegions.empty())
+    // Prevent the orphan section to be placed before the found section. If
+    // custom program headers are defined, that helps to avoid adding it to a
+    // previous segment and changing flags of that segment, for example, making
+    // a read-only segment writable. If memory regions are defined, an orphan
+    // section should continue the same region as the found section to better
+    // resemble the behavior of GNU ld.
     sortRank = std::max(sortRank, foundSec->sortRank);
   for (; i != e; ++i) {
     auto *curSec = dyn_cast<OutputSection>(*i);
     if (!curSec || !curSec->hasInputSections)
       continue;
     if (getRankProximity(sec, curSec) != proximity ||
         sortRank < curSec->sortRank)
       break;

lld/test/ELF/linkerscript/orphan-memory.test

+REQUIRES: x86
+
+RUN: split-file %s %ts
+RUN: llvm-mc -filetype=obj -triple=x86_64 %ts/s -o %t.o
+
+## Check that despite having a lower sort rank, an orphan section '.init_array'
+## is placed after '.data' and '.data2' and in the same memory region.
+
+## Also check that a non-SHF_ALLOC orphan section '.nonalloc' is not placed in
+## a memory region. Both defined memory regions are exhausted after all expected
+## sections are added, thus, trying to put any unexpected section would lead to
+## an error.
+
+RUN: ld.lld -o %t -T %ts/t %t.o
+RUN: llvm-readelf -S %t | FileCheck %s
+
+CHECK: Name        Type       Address          Off           Size
+CHECK: .text       PROGBITS   0000000000008000 {{[0-9a-f]+}} 000004
+CHECK: .data       PROGBITS   0000000000009000 {{[0-9a-f]+}} 000008
+CHECK: .data2      PROGBITS   0000000000009008 {{[0-9a-f]+}} 00000c
+CHECK: .init_array INIT_ARRAY 0000000000009014 {{[0-9a-f]+}} 000010
+CHECK: .nonalloc   PROGBITS   0000000000000000 {{[0-9a-f]+}} 000010
+
+## Check that attributes of memory regions are ignored for orphan sections when
+## the anchor section specifies the memory region explicitly, This seems to
+## contradict https://sourceware.org/binutils/docs/ld/MEMORY.html, but better
+## resembles the way GNU ld actually works.
+
+RUN: ld.lld -o %t2 -T %ts/t2 %t.o
+RUN: llvm-readelf -S %t2 | FileCheck %s
+
+## Same as the previous case, but now properties of sections conflict with
+## memory region attributes. Still, orphan sections are placed in the same
+## regions as their anchors.
+
+RUN: ld.lld -o %t3 -T %ts/t3 %t.o
+RUN: llvm-readelf -S %t3 | FileCheck %s
+
+## Check that when memory regions for anchor sections are not specified
+## explicitly and are selected by attributes, orphan sections are also assigned
+## to memory regions by matching properties.
+
+RUN: ld.lld -o %t4 -T %ts/t4 %t.o
+RUN: llvm-readelf -S %t4 | FileCheck %s --check-prefix=CHECK4
+
+CHECK4: Name        Type       Address          Off           Size
+CHECK4: .text       PROGBITS   0000000000008000 {{[0-9a-f]+}} 000004
+CHECK4: .init_array INIT_ARRAY 0000000000009000 {{[0-9a-f]+}} 000010
+CHECK4: .data       PROGBITS   0000000000009010 {{[0-9a-f]+}} 000008
+CHECK4: .data2      PROGBITS   0000000000009018 {{[0-9a-f]+}} 00000c
+CHECK4: .nonalloc   PROGBITS   0000000000000000 {{[0-9a-f]+}} 000010
+
+#--- s
+  .text
+  .zero 4
+
+  .data
+  .zero 8
+
+  .section .data2,"aw",@progbits
+  .zero 0xc
+
+  .section .init_array,"aw",@init_array
+  .zero 0x10
+
+  .section .nonalloc,""
+  .zero 0x10
+
+#--- t
+MEMORY
+{
+  TEXT : ORIGIN = 0x8000, LENGTH = 0x4
+  DATA : ORIGIN = 0x9000, LENGTH = 0x24
+}
+
+SECTIONS
+{
+  .text : { *(.text) } > TEXT
+  .data : { *(.data) } > DATA
+}
+
+#--- t2
+MEMORY
+{
+  TEXT (rwx) : ORIGIN = 0x8000, LENGTH = 0x4
+  DATA (rwx) : ORIGIN = 0x9000, LENGTH = 0x24
+}
+
+SECTIONS
+{
+  .text : { *(.text) } > TEXT
+  .data : { *(.data) } > DATA
+}
+
+#--- t3
+MEMORY
+{
+  TEXT (!w) : ORIGIN = 0x8000, LENGTH = 0x4
+  DATA (!w) : ORIGIN = 0x9000, LENGTH = 0x24
+}
+
+SECTIONS
+{
+  .text : { *(.text) } > TEXT
+  .data : { *(.data) } > DATA
+}
+
+#--- t4
+MEMORY
+{
+  TEXT (rx)  : ORIGIN = 0x8000, LENGTH = 0x4
+  DATA (w!x) : ORIGIN = 0x9000, LENGTH = 0x24
+}
+
+SECTIONS
+{
+  .text : { *(.text) }
+}