[ELF] Propagate phdrs to orphan section with a smaller rank

[ikudrin]

Summary

In a case when segments are explicitly defined in a linker script, and if an orphan section is placed before the section with the closest sort rank, it may be put in the previous segment, which can affect the flags of that segment. The patch fixes the issue by assigning segments from the found section to the orphan section.

[jhenderson]

My memory of how this area of code works is a bit hazy, so it's probably beset if @MaskRay or @psmith take a look.

[peter.smith]

Will take a closer next week unless MaskRay gets a chance and is happy.

Intuitively I think this is right; if we have an orphan on the boundary between two segments, it makes sense to place in the segment with compatible flags. Will need to check through the details, and see if there is any prior art in ld.bfd.

[MaskRay]

Fix assigning segments to orphan sections

I'd not use "Fix". It makes a case more user-friendly but does not necessarily mean we have a bug.
I may use something like: Propagate phdrs to orphan section with a smaller rank.

One practical problem is that the rule of thumb "the first output section of each segment should be specified" is not communicated among users.

---

I have a mixed feeling on this patch. It does make it a bit more user-friendly for the added case by not making the non-PF_W segment PF_W.
If we make this change:

 PHDRS {
-  exec PT_LOAD;
-  rw   PT_LOAD;
+  exec PT_LOAD FLAGS(0x5);
+  rw   PT_LOAD FLAGS(0x6);
 }

Program Headers:
  Type           Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
  LOAD           0x001000 0x0000000000000000 0x0000000000000000 0x0000e0 0x0000e0 R E 0x1000
  LOAD           0x0010e0 0x00000000000000e0 0x00000000000000e0 0x000008 0x000008 RW  0x1000

 Section to Segment mapping:
  Segment Sections...
   00     .dynsym .gnu.hash .hash .dynstr .text .dynamic 
   01     .data

Our current behavior is problematic.

However,

• the new logic is inconsistent when the PHDRS command is not used.
• it duplicates the maybePropagatePhdrs phdrs propagation logic in a different place

In addition, the original rationale is not sufficient justifying.
From https://maskray.me/blog/2021-07-04-sections-and-overwrite-sections, when linking a regular program, if one really wants to use a linker script, the linker script should at least specify the first output section of each segment, specifically including the first output section of PT_GNU_RELRO. A minimal example:

text
SECTIONS
{
  PROVIDE (__executable_start = SEGMENT_START("text-segment", 0x400000)); . = SEGMENT_START("text-segment", 0x400000) + SIZEOF_HEADERS;

  . = DATA_SEGMENT_ALIGN (CONSTANT (MAXPAGESIZE), CONSTANT (COMMONPAGESIZE));
  .init_array    :
  {
    PROVIDE_HIDDEN (__init_array_start = .);
    KEEP (*(SORT_BY_INIT_PRIORITY(.init_array.*)))
    KEEP (*(.init_array))
    PROVIDE_HIDDEN (__init_array_end = .);
  }
  .fini_array    :
  {
    PROVIDE_HIDDEN (__fini_array_start = .);
    KEEP (*(SORT_BY_INIT_PRIORITY(.fini_array.*)))
    KEEP (*(.fini_array))
    PROVIDE_HIDDEN (__fini_array_end = .);
  }
  . = DATA_SEGMENT_RELRO_END (0, .);
  .data           : { *(.data .data.*) }
  . = .;
  .bss            : { *(.bss .bss.*) *(COMMON) }
  . = DATA_SEGMENT_END (.);
}

I haven't formed my opinion completely, and want to hear from Peter, but do have some concern on the current implementation.

lld/ELF/Writer.cpp

1263

"corrupt" is inaccurate. A non-PF_W segment may now become PF_W, but it is not corrupted.

1265

&& foundSec->hasInputSections can be deleted

[ikudrin]

• Updated the title
• Updated the comment
• Removed && foundSec->hasInputSections

In D111137#3053918, @MaskRay wrote:

Fix assigning segments to orphan sections

I'd not use "Fix". It makes a case more user-friendly but does not necessarily mean we have a bug.
I may use something like: Propagate phdrs to orphan section with a smaller rank.

Thanks for the suggestion!

One practical problem is that the rule of thumb "the first output section of each segment should be specified" is not communicated among users.

A user may not be aware of all the nuances of the linker. For example, they might switch from a different linker that had different rules to place orphan sections and just continue using the same linker script that already worked for them.

• the new logic is inconsistent when the PHDRS command is not used.

If no PHDRS is used, the new segment will start at the orphan section which is placed before the found section. From this perspective, the new logic works similarly.

• it duplicates the maybePropagatePhdrs phdrs propagation logic in a different place

Right, and it also modifies its data, which is usually not expected in a find function.

Alternatively, we can place orphan sections after the closest-rank section, even if their sort rank is smaller. This may relieve the concerns, in the cost of slightly changing the resulting layout.

[peter.smith]

Looking at GNU ld and the documentation for PHDRS https://sourceware.org/binutils/docs/ld/PHDRS.html

If you place a section in one or more segments using ‘:phdr’, then the linker will place all subsequent allocatable sections which do not specify ‘:phdr’ in the same segments. This is for convenience, since generally a whole set of contiguous sections will be placed in a single segment. You can use :NONE to override the default segment and tell the linker to not put the section in any segment at all.

This would imply that if .dynamic were placed before .data, implicitly making the script

PHDRS {
  exec PT_LOAD;
  rw   PT_LOAD;
}
SECTIONS {
  .text : { *(.text) } : exec
  .dynamic : { *(.dynamic) } /* No explicit program header, inherit from previous */
  .data : { *(.data) } : rw
}

Then ld.bfd does what LLD does and makes the first program header writeable.

When trying the same example with ld.bfd I notice that it assigns .dynamic after .data when .dynamic is an orphan.

.text           0x0000000000008000        0x1
 *(.text)
 .text          0x0000000000008000        0x1 orphan.o

.plt            0x0000000000008010        0x0
 .plt           0x0000000000008010        0x0 orphan.o

.plt.got        0x0000000000008008        0x0
 .plt.got       0x0000000000008008        0x0 orphan.o

.interp         0x0000000000008001        0xf
 .interp        0x0000000000008001        0xf orphan.o

.gnu.version_d  0x0000000000008010        0x0
 .gnu.version_d
                0x0000000000008010        0x0 orphan.o

.gnu.version    0x0000000000008010        0x0
 .gnu.version   0x0000000000008010        0x0 orphan.o

.gnu.version_r  0x0000000000008010        0x0
 .gnu.version_r
                0x0000000000008010        0x0 orphan.o

.dynsym         0x0000000000008010       0x18
 .dynsym        0x0000000000008010       0x18 orphan.o

.dynstr         0x0000000000008028        0x1
 .dynstr        0x0000000000008028        0x1 orphan.o

.hash           0x0000000000008030       0x10
 .hash          0x0000000000008030       0x10 orphan.o

.gnu.hash       0x0000000000008040       0x1c
 .gnu.hash      0x0000000000008040       0x1c orphan.o

.eh_frame       0x0000000000008060        0x0
 .eh_frame      0x0000000000008060        0x0 orphan.o
 .eh_frame      0x0000000000008060        0x0 orphan.o

.rela.dyn       0x0000000000008060        0x0
 .rela.plt      0x0000000000008060        0x0 orphan.o
 .rela.got      0x0000000000008060        0x0 orphan.o
 .rela.bss      0x0000000000008060        0x0 orphan.o
 .rela.data.rel.ro
                0x0000000000008060        0x0 orphan.o
 .rela.ifunc    0x0000000000008060        0x0 orphan.o
.data           0x000000000000805c        0x2
 *(.data)
 .data          0x000000000000805c        0x2 orphan.o
OUTPUT(orphan elf64-x86-64)

.dynamic        0x0000000000008060       0xe0
 .dynamic       0x0000000000008060       0xe0 orphan.o
                0x0000000000008060                _DYNAMIC

.got            0x0000000000008140        0x0
 .got           0x0000000000008140        0x0 orphan.o

.got.plt        0x0000000000008140        0x0
 .got.plt       0x0000000000008140        0x0 orphan.o

.data.rel.ro    0x0000000000008140        0x0
 .data.rel.ro   0x0000000000008140        0x0 orphan.o

.dynbss         0x0000000000008140        0x0
 .dynbss        0x0000000000008140        0x0 orphan.o

To be consistent with ld.bfd would it be better to look at the orphan placement of .dynamic?

[ikudrin]

In D111137#3055278, @peter.smith wrote:

To be consistent with ld.bfd would it be better to look at the orphan placement of .dynamic?

Maybe they just always place orphan sections after defined ones? I've made a patch implementing that, please take a look: D111717.

[peter.smith]

Thanks for the update. I'll put my comments here as I did a bit more digging into ld.bfd's orphan placement section. At a high-level It looks like they have anchor sections with known flags that orphans are placed after. In particular:

.text
.rodata
.tdata
.data
.bss
.interp
.sdata
.comment

It does not consider relro at all. So .dynamic is matched against .data and is placed afterwards. This makes the linker script assign two program headers but turns off RELRO.

I think that this makes sense given the definition of PHDRS as it says only generate PHDRS explicitly specified and this doesn't include PT_DYNAMIC or PT_GNU_RELRO. ld.bfd does not even accept PT_GNU_RELRO and at least the version of bfd I've got installed crashes when I use its numeric value.

I think to support RELRO we'd need something like:

PHDRS {
  exec PT_LOAD;
  rw   PT_LOAD;
  dynamic PT_DYNAMIC;
  relro 1685382482;
}
SECTIONS {
  .text 0x8000 : { *(.text) } : exec
  .dynamic : { *(.data) } : rw : dynamic : relro
  .data : { *(.data) } : rw
}

I've not got a great answer for what we ought to do. It seems like relro + PHDRS is not supported well right now with BFD. In that case I think we could do one of:

• Disable RELRO if there is a PT_PHDRS command, this would make .dynamic sort behind .data and avoid other attempts at creating relro.
• Add support for a PT_GNU_RELRO program header and require this before enabling relro. User will have to be quite explicit about what parts go into it though.

If we do one of these then I think the desired behaviour should drop out from your example linker script.

[ikudrin]

While disabling RELRO fixes the particular example, it is not the ultimate solution for the issue. It does not help, for example, if .data is replaced with .bss in the test:

> cat test.s
  .text
  nop

  .bss
  .quad 0
> cat test.lds
PHDRS {
  exec PT_LOAD;
  rw   PT_LOAD;
}
SECTIONS {
  .text : { *(.text) } : exec
  .bss : { *(.bss) } : rw
}
> llvm-mc -filetype=obj -triple=x86_64 test.s -o test.o
> ld.lld -z norelro -pie test.o -T test.lds -o test.out
> llvm-readelf -l test.out
...
Program Headers:
  Type           Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
  LOAD           0x001000 0x0000000000000000 0x0000000000000000 0x0000e0 0x0000e0 RWE 0x1000
  LOAD           0x0010e0 0x00000000000000e0 0x00000000000000e0 0x000000 0x000008 RW  0x1000

 Section to Segment mapping:
  Segment Sections...
   00     .dynsym .gnu.hash .hash .dynstr .text .dynamic 
   01     .bss 
   None   .comment .symtab .shstrtab .strtab

[peter.smith]

That is true, although it is the same result in ld.bfd (slightly different using AArch64 but comparable).

Elf file type is EXEC (Executable file)
Entry point 0x8000
There are 2 program headers, starting at offset 64

Program Headers:
  Type           Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
  LOAD           0x008000 0x0000000000008000 0x0000000000008000 0x000170 0x000170 RWE 0x10000
  LOAD           0x008170 0x0000000000008170 0x0000000000008170 0x000000 0x000004 RW  0x10000

 Section to Segment mapping:
  Segment Sections...
   00     .text .interp .dynsym .dynstr .hash .gnu.hash .dynamic .got .got.plt
   01     .bss
   None   .symtab .strtab .shstrtab

I guess it comes down to how we interpret the PHDRS documentation https://sourceware.org/binutils/docs/ld/PHDRS.html do we assume that people using PHDRS are doing so for maximum control and it is up to the user to give enough direction in their linker script for LLD to do what they want. Or do we try and interpret the PHDRS and say you probably meant to do this. I think both are reasonable positions. I personally come down in favour of staying as close to ld.bfd as possible as that is where projects are migrated from, but happy to accept the alternative if MaskRay would prefer that direction.

[ikudrin]

If a user fully specified their intentions in the linker script, there is no room for orphan sections; if there are orphan sections, then it is your second case. As the documentation says nothing about placing orphan sections and assigning them to segments, the linkers can cook up their own rules that seem sensible, and the rule to put an orphan section into the same segment as the most similar one seems reasonable to me.

[ikudrin]

Abandon in favor of D111717.

lld/ELF/Writer.cpp

findOrphanPos(std::vector<BaseCommand *>::iterator b,
 
   // Find the first element that has as close a rank as possible.
   auto i = std::max_element(b, e, [=](BaseCommand *a, BaseCommand *b) {
     return getRankProximity(sec, a) < getRankProximity(sec, b);
   });
   if (i == e)
     return e;
 
+  // If the orphan section is going to be placed before the found section,
+  // inherit explicitly specified segments from that section. Otherwise,
+  // the orphan section may be placed in the previous segment, which may
+  // corrupt its flags.
+  auto foundSec = dyn_cast<OutputSection>(*i);
+  if (script->hasPhdrsCommands() && foundSec && foundSec->hasInputSections &&
+      sec->sortRank < foundSec->sortRank)
+    sec->phdrs = foundSec->phdrs;
+
   // Consider all existing sections with the same proximity.
   int proximity = getRankProximity(sec, *i);
   for (; i != e; ++i) {
     auto *curSec = dyn_cast<OutputSection>(*i);
     if (!curSec || !curSec->hasInputSections)
       continue;
     if (getRankProximity(sec, curSec) != proximity ||
         sec->sortRank < curSec->sortRank)

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

+# REQUIRES: x86
+
+# RUN: split-file %s %ts
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %ts/s -o %t.o
+# RUN: ld.lld -pie -o %t -T %ts/t %t.o
+# RUN: llvm-readelf -l %t | FileCheck %s
+
+## Check that an orphan section '.dynamic' is added to the same segment as
+## its closest-rank section '.data', even though it is placed before '.data'.
+## Adding 'dynamic' to the first segment would make the segment writable.
+# CHECK:     LOAD {{.*}} R E
+# CHECK:     LOAD {{.*}} RW
+
+# CHECK:     Segment Sections...
+# CHECK-NOT: 00{{.*}} .dynamic
+# CHECK:     01 .dynamic .data
+
+#--- s
+  .text
+  nop
+
+  .data
+  .quad 0
+
+#--- t
+PHDRS {
+  exec PT_LOAD;
+  rw   PT_LOAD;
+}
+SECTIONS {
+  .text : { *(.text) } : exec
+  .data : { *(.data) } : rw
+}