[ELF] Merge PT_LOAD segments in case they have different attributes and reside in the same memory page

[evgeny777]

Summary

Currently linker script support in lld is almost useless due to following reasons:

1. First PT_LO`D segment always has zero virtual address (see http://reviews.llvm.org/D21750)
2. PT_LOAD segments are very often not aligned correctly, because section grouping is not yet implemented

Consider the following script:

SECTIONS  {
   . = 0x10000000;
   .bss : { *(.bss) }
   .data : { *(.data) }
   . = 0x11000000;
   .text : { *(.text) }
 }

And the following C code:

int main(void) { return 0; }

Compiling and linking it using lld and script provided will result in ELF having following segments:

LOAD  0x002000 0x0000000011000000 0x0000000011000000 0x182 0x182 R E
LOAD  0x002184 0x0000000011000184 0x0000000011000184 0x1d0 0x1d0 R
LOAD  0x002354 0x0000000011000354 0x0000000011000354 0x04c 0x04c R E 
LOAD  0x0023a0 0x00000000110003a0 0x00000000110003a0 0x188 0x188 RW

Linux kernel will map them one by one to virtual address 0x11000000 (page-aligned), with map size of 0x1000 (page rounded)
and different protection attributes. Finally one will have region 0x11000000 - 0x11001000 mapped with RW attributes. Jumping to
entry point 0x11000000 will immediately cause protection fault (SIGSEGV). Not a single user instruction will be executed

To (temporary) overcome this problem and generate working image I propose to merge PT_LOAD segments ORing protection attributes
(this is, to my beleif, gold linker does). After merge one will have a single PT_LOAD segment:

LOAD  0x002000 0x0000000011000000 0x0000000011000000 0x528 0x528 RWE

As now segment has RWE protection attributes user instructions can be executed normally.

[ruiu]

Does merging attributes produce a desired result? It seems to me that it would silently produce writable text segments or something like that, which seems even dangerous. I'd think what we should do instead is to group input sections by attributes and put sections with different attributes into different pages.

[evgeny777]

Grouping sections doesn't mean you won't have this problem. Consider this script

SECTIONS  {
   . = 0x10000000;
   .text : { *(.text) }
   . = 0x10001000;
    .data : { *(.data) }
}

The gap between .text and .data may be too small to put .plt, .fini and other executable sections, so you can't group them together and have to put
them to the end of the file with other sections (like gold does)

I tried starting sections from new page in case there is an attribute conflict, but it breaks a lot of existing tests. It can probably break something else.
Do you think this is a better approach?

[evgeny777]

A small addition:

Have two segments:

LOAD  0x002354 0x0000000011000354 0x0000000011000354 0x04c 0x04c R E 
LOAD  0x0023a0 0x00000000110003a0 0x00000000110003a0 0x188 0x188 RWE

Will also make segment 0x10000000 - 0x10001000 writeable. So protection violation already exists

[ruiu]

So the reason why we end up with a page that needs to have merged page attributes is because we layout sections without any padding in between, right?

Usually, when you give a section script to enforce layout, your section layout usually do not try to put different sections into the same page (and I think it's a good thing and we should report an error otherwise.)

However, if a linker script does not specify a layout for *all* sections, we place remaining sections at end of file without any padding. I think it is the problem. I believe we need to add padding in that case.

[evgeny777]

Like I said, this was the first thing I tried, but it breaks about 7 unit tests (though all are related to scripting).
How to handle this? Update exisiting test cases?

[ruiu]

Please update unit tests. They are not golden tests, but they just reflect our current understanding how the linker should behave.

[evgeny777]

Diff updated.

Instead of checking if any two sections with different attributes share the same memory page, I check if two consecutive sections reside in different PT_LOAD segments.
If so I do page aligning for a section. The desired behavior (padding) is achieved due to createPhdrs() creates new PT_LOAD segment if section attributes are different from those of previous one.

The next thing I plan to implement is support of PHDRS directive and section-to-segment assignments. In such case sections with different attributes may reside in a single PT_LOAD segment (which has its own attributes specified inside PHDRS block). The algorithm described above will work correctly in this case as well.

[evgeny777]

Any comments on this?

[ruiu]

ELF/LinkerScript.cpp

247

You have two spaces between * and PrevSec.

271–273

You want to place a section to a new pace if the section's attribute is different from the previous one, right?

You can have a previous attribute as a local variable in this function instead of defining a set of functions for Anchor sections, no?

[evgeny777]

ELF/LinkerScript.cpp

271–273

Not exactly. I want to place section to a new page if it is located in a different PT_LOAD segment with previous one.
Current version creates new PT_LOAD segment for a section if it has different attributes with previous one (see createPhdrs).
So comparing PT_LOAD segments has exactly the same effect as comparing section attributes

But consider you have this linker script

PHDRS {
    myheader : PT_LOAD FLAGS 7; / * 7 means PF_R | PF_W | PF_X */
}

SECTIONS {
  .text : { *(.text) } : myheader
  .data : { *(.text) } : myheader
}

This linker script forces .text (RX) and .data (RW) to be placed to a same PT_LOAD with RWX attributes. Placing .data section to a new page will simply waste memory and space in ELF image.

[ruiu]

We do not support FLAGS, so we don't need to care about that at this moment.

[evgeny777]

Yes, I know :).
But the reason, I'm doing this is that I want to implement script support.

[ruiu]

Well, in general, I prefer simple code that is enough to support a feature than more complex code that "prepares" for future enhancements. You can always add code when you need it.

[evgeny777]

Diff updated.
Now it updates section VAs in case they share the same memory page and have conflicting attributes.
This is done only in case they are not mentioned in the linker script (so called orphaned sections).

[ruiu]

ELF/LinkerScript.cpp

211

Likewise, IsOrphan.

216

Why do you have to distinguish orphaned sections and non-orphaned sections? I think we reserve the right to order orphaned sections in any way (our current layout is different from gold or bfd), and I don't see a reason to handle them specially.

ELF/LinkerScript.h

49

Let's name this IsOrphan.

ELF/Target.h

109–111

I think this is not generic enough to put it in this header because you are using it in only one file. I'd move this to LinkerScript.cpp (and rename getPageNumber).

Please rename address -> Address (but I'd name Addr). Parameter names should start with lowercase letters.

[evgeny777]

ELF/LinkerScript.cpp

216

I think that it's up to user to specify correct alignment of sections listed in linker script, so I don't do anything for them (garbage in - garbage out)
Orphaned sections are not listed in linker script, so (I think) I can fix their alignment
You thoughts?

[ruiu]

ELF/LinkerScript.cpp

216

Is there any problem if you unconditionally align a section to a new page boundary if attributes of the section is different from attributes of the previous section? I mean, if a user specifies impossible layout (by trying to putting different kind of sections to the same page), I think it is okay to do whatever we think sane.

[grimar]

Eugene, please update this and others patches you posted to have llvm-commits in subscribers.
Otherwise probably nobody except reviewers you assigned are able to notice them. Thanks !

[grimar]

ELF/LinkerScript.cpp

215

btw, may be it is worth to change getAlignment to return unsigned ?
(not relative to this patch, but can help to remove static cast below)

218

variable names should be uppercase.

[evgeny777]

Not needed any longer

ELF/LinkerScript.h

 // ExprKind is a location counter change, like ". = . + 0x1000"
 // SectionKind is a description of output section, like ".data :..."
 enum SectionsCommandKind { ExprKind, SectionKind };
 
 struct SectionsCommand {
   SectionsCommandKind Kind;
   std::vector<StringRef> Expr;
   StringRef SectionName;
+  bool IsFromParser;
 };
 
 // ScriptConfiguration holds linker script parse results.
 struct ScriptConfiguration {
   // SECTIONS commands.
   std::vector<SectionRule> Sections;
 
   // Section fill attribute for each section.

ELF/LinkerScript.cpp

 bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
   for (StringRef Pat : Opt.KeptSections)
     if (globMatch(Pat, S->getSectionName()))
       return true;
   return false;
 }
 
 template <class ELFT>
+static typename ELFT::uint calculateSectionVA(typename ELFT::uint VA,
+                                              bool sectionIsFromParser,
+                                              OutputSectionBase<ELFT> *PrevSec,
+                                              OutputSectionBase<ELFT> *Sec) {
+  typedef typename ELFT::uint uintX_t;
+  uintX_t Alignment = Sec->getAlignment();
+  if (PrevSec && !sectionIsFromParser) {
+    uintX_t secAttrs = Sec->getFlags() & (SHF_EXECINSTR | SHF_WRITE);
+    uintX_t prevSecAttrs = PrevSec->getFlags() & (SHF_EXECINSTR | SHF_WRITE);
+
+    if (secAttrs != prevSecAttrs &&
+        pageNo(VA) == pageNo(PrevSec->getVA() + PrevSec->getSize()))
+      Alignment = std::max(Alignment, static_cast<uintX_t>(Target->PageSize));
+  }
+  VA = alignTo(VA, Alignment);
+  return VA;
+}
+
+template <class ELFT>
 void LinkerScript<ELFT>::assignAddresses(
     ArrayRef<OutputSectionBase<ELFT> *> Sections) {
   // Orphan sections are sections present in the input files which
   // are not explicitly placed into the output file by the linker script.
   // We place orphan sections at end of file.
   // Other linkers places them using some heuristics as described in
   // https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections.
   for (OutputSectionBase<ELFT> *Sec : Sections) {
     StringRef Name = Sec->getName();
     if (getSectionIndex(Name) == INT_MAX)
-      Opt.Commands.push_back({SectionKind, {}, Name});
+      Opt.Commands.push_back({SectionKind, {}, Name, false});
   }
 
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   Dot = Out<ELFT>::ElfHeader->getSize() + Out<ELFT>::ProgramHeaders->getSize();
   uintX_t MinVA = std::numeric_limits<uintX_t>::max();
+  OutputSectionBase<ELFT> *PrevSec = nullptr;
   uintX_t ThreadBssOffset = 0;
 
   for (SectionsCommand &Cmd : Opt.Commands) {
     if (Cmd.Kind == ExprKind) {
       Dot = evalExpr(Cmd.Expr, Dot);
       continue;
     }
 
     // Find all the sections with required name. There can be more than
     // ont section with such name, if the alignment, flags or type
     // attribute differs.
     for (OutputSectionBase<ELFT> *Sec : Sections) {
       if (Sec->getName() != Cmd.SectionName)
         continue;
 
       if ((Sec->getFlags() & SHF_TLS) && Sec->getType() == SHT_NOBITS) {
         uintX_t TVA = Dot + ThreadBssOffset;
         TVA = alignTo(TVA, Sec->getAlignment());
         Sec->setVA(TVA);
         ThreadBssOffset = TVA - Dot + Sec->getSize();
         continue;
       }
 
       if (Sec->getFlags() & SHF_ALLOC) {
-        Dot = alignTo(Dot, Sec->getAlignment());
+        Dot = calculateSectionVA(Dot, Cmd.IsFromParser, PrevSec, Sec);        
         Sec->setVA(Dot);
         MinVA = std::min(MinVA, Dot);
         Dot += Sec->getSize();
+        PrevSec = Sec;
         continue;
       }
     }
   }
 
   // ELF and Program headers need to be right before the first section in memory.
   // Set their addresses accordingly.
   MinVA = alignDown(MinVA - Out<ELFT>::ElfHeader->getSize() -
while (!Error && !skip("}")) {
     else
       readOutputSectionDescription();
   }
 }
 
 void ScriptParser::readLocationCounterValue() {
   expect(".");
   expect("=");
-  Opt.Commands.push_back({ExprKind, {}, ""});
+  Opt.Commands.push_back({ExprKind, {}, "", true});
   SectionsCommand &Cmd = Opt.Commands.back();
   while (!Error) {
     StringRef Tok = next();
     if (Tok == ";")
       break;
     Cmd.Expr.push_back(Tok);
   }
   if (Cmd.Expr.empty())
     error("error in location counter expression");
 }
 
 void ScriptParser::readOutputSectionDescription() {
   StringRef OutSec = next();
-  Opt.Commands.push_back({SectionKind, {}, OutSec});
+  Opt.Commands.push_back({SectionKind, {}, OutSec, true});
   expect(":");
   expect("{");
 
   while (!Error && !skip("}")) {
     StringRef Tok = next();
     if (Tok == "*") {
       expect("(");
       while (!Error && !skip(")"))

ELF/Target.h

 
 StringRef getRelName(uint32_t Type);
 uint64_t getPPC64TocBase();
 
 const unsigned MipsGPOffset = 0x7ff0;
 
 extern TargetInfo *Target;
 TargetInfo *createTarget();
+
+template <class T> static inline T pageNo(T address) {
+  return address / Target->PageSize;
+}
 }
 }
 
 #endif

test/ELF/end.s

 
 // NOBSS: Sections [
 // NOBSS:     Name: .data
 // NOBSS-NEXT:     Type:
 // NOBSS-NEXT:     Flags [
 // NOBSS-NEXT:       SHF_ALLOC
 // NOBSS-NEXT:       SHF_WRITE
 // NOBSS-NEXT:     ]
-// NOBSS-NEXT:     Address: 0x159
+// NOBSS-NEXT:     Address: 0x1000
 // NOBSS-NEXT:     Offset:
 // NOBSS-NEXT:     Size: 2
 // NOBSS: ]
 // NOBSS: Symbols [
 // NOBSS:     Name: _end
-// NOBSS-NEXT:     Value: 0x15B
+// NOBSS-NEXT:     Value: 0x1002
 // NOBSS: ]
 
 // If the layout of the sections is changed, "_end" should point to the end of allocated address space.
 // RUN: echo "SECTIONS { \
 // RUN:          .bss : { *(.bss) } \
 // RUN:          .data : { *(.data) } \
 // RUN:          .text : { *(.text) } }" > %t.script
 // RUN: ld.lld %t.o --script %t.script -o %t

test/ELF/linkerscript-repsection-va.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 
 # RUN: echo "SECTIONS {.foo : {*(.foo.*)} }" > %t.script
 # RUN: ld.lld -o %t1 --script %t.script %t
 # RUN: llvm-objdump -section-headers %t1 | FileCheck %s
 # CHECK:      Sections:
 # CHECK-NEXT: Idx Name          Size      Address          Type
 # CHECK-NEXT:   0               00000000 0000000000000000
 # CHECK-NEXT:   1 .foo          00000004 0000000000000158 DATA
 # CHECK-NEXT:   2 .foo          00000004 000000000000015c DATA
-# CHECK-NEXT:   3 .text         00000001 0000000000000160 TEXT DATA
+# CHECK-NEXT:   3 .text         00000001 0000000000001000 TEXT DATA
 
 .global _start
 _start:
  nop
 
 .section .foo.1,"a"
 foo1:
  .long 0
 
 .section .foo.2,"aw"
 foo2:
  .long 0

test/ELF/linkerscript-sections-keep.s

 # RUN:  .nokeep : { *(.keep) }}" > %t.script
 # RUN: ld.lld --gc-sections -o %t1 --script %t.script %t
 # RUN: llvm-objdump -section-headers %t1 | FileCheck -check-prefix=MIXED1 %s
 # MIXED1:      Sections:
 # MIXED1-NEXT: Idx Name          Size      Address         Type
 # MIXED1-NEXT:   0               00000000 0000000000000000
 # MIXED1-NEXT:   1 .keep         00000004 0000000000000120 DATA
 # MIXED1-NEXT:   2 .temp         00000004 0000000000000124 DATA
-# MIXED1-NEXT:   3 .text         00000007 0000000000000128 TEXT DATA
+# MIXED1-NEXT:   3 .text         00000007 0000000000001000 TEXT DATA
 # MIXED1-NEXT:   4 .symtab       00000060 0000000000000000
 # MIXED1-NEXT:   5 .shstrtab     0000002d 0000000000000000
 # MIXED1-NEXT:   6 .strtab       00000012 0000000000000000
 
 ## The same, but now section without KEEP is at first place.
 ## gold and bfd linkers disagree here. gold collects .keep while
 ## bfd keeps it. Our current behavior is compatible with bfd although
 ## we can choose either way.
 # RUN: echo "SECTIONS { \
 # RUN:  .nokeep : { *(.keep) } \
 # RUN:  .keep : { KEEP(*(.keep)) }}" > %t.script
 # RUN: ld.lld --gc-sections -o %t1 --script %t.script %t
 # RUN: llvm-objdump -section-headers %t1 | FileCheck -check-prefix=MIXED2 %s
 # MIXED2:      Sections:
 # MIXED2-NEXT: Idx Name          Size      Address         Type
 # MIXED2-NEXT:   0               00000000 0000000000000000
 # MIXED2-NEXT:   1 .nokeep       00000004 0000000000000120 DATA
 # MIXED2-NEXT:   2 .temp         00000004 0000000000000124 DATA
-# MIXED2-NEXT:   3 .text         00000007 0000000000000128 TEXT DATA
+# MIXED2-NEXT:   3 .text         00000007 0000000000001000 TEXT DATA
 # MIXED2-NEXT:   4 .symtab       00000060 0000000000000000
 # MIXED2-NEXT:   5 .shstrtab     0000002f 0000000000000000
 # MIXED2-NEXT:   6 .strtab       00000012 0000000000000000
 
 .global _start
 _start:
  mov temp, %eax
 
 .section .keep, "a"
 keep:
  .long 1
 
 .section .temp, "a"
 temp:
  .long 2

test/ELF/linkerscript-va.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 
 # RUN: echo "SECTIONS {}" > %t.script
 # RUN: ld.lld -o %t1 --script %t.script %t
 # RUN: llvm-objdump -section-headers %t1 | FileCheck %s
 # CHECK:      Sections:
 # CHECK-NEXT: Idx Name          Size      Address          Type
 # CHECK-NEXT:   0               00000000 0000000000000000
 # CHECK-NEXT:   1 .foo          00000004 0000000000000120 DATA
 # CHECK-NEXT:   2 .boo          00000004 0000000000000124 DATA
-# CHECK-NEXT:   3 .text         00000001 0000000000000128 TEXT DATA
+# CHECK-NEXT:   3 .text         00000001 0000000000001000 TEXT DATA
 
 .global _start
 _start:
  nop
 
 .section .foo, "a"
 foo:
  .long 0
 
 .section .boo, "a"
 boo:
  .long 0