Mitigate relocation overflow [part 1 of 2]

[shenhan]

Summary

This CL is to mitigate R_X86_64_PC32 relocation overflow problems for huge binaries that has near 2G allocated sections.

By examining those binaries, I found these 2 issues contributes to the problem:
1). huge ".dynsym" and ".dynstr" stands in the way between .rodata and .text
2). _init_array_start/end are placed at 0 if no ".init_array" presents, this causes .text relocation against them become more prone to overflow.

This CL addresses 1st problem (the 2nd will be addressed in another CL.) by assigning a smaller sortrank to .dynsym and .dynstr thus they no longer stand in between

Note: this CL affects multiple tests, I include in this CL only 2 of many changes to the tests. And I'll provide the rest once this main part of this CL gets approved.

[ruiu]

ELF/Writer.cpp

721–722

Please expand the comment to explain that we want to put progbits sections closer so that relocations as an effort to prevent relocation overflow between these sections.

722

What is this isRelroSection condition for?

1694

Please use clang-format.

I think that Config->ImageBase is a better default value than an address of .text section because a section whose name is .text may not exist.

[shenhan]

ELF/Writer.cpp

722

This is used to skip reordering for relro sections, because these to be put into RelRo segment must be contiguous, otherwise lld complains.

1694

Done clang-format.

In some cases, Config->ImageBase is too small, like I see 0x1000. And 0x1000 is still too far away from some .text sections.

[ruiu]

ELF/Writer.cpp

722

How did it work before this patch? I thought that all relro sections are progbits sections, so setting PF_PROGBITS to everybody doesn't change the existing behavior. It is confusing if you don't set RF_PROGBITS to everybody unconditionally.

1693–1697

Please find .text section outside of this lambda to call findSection only once.

p needs to be P by the LLVM coding style. But I prefer Text.

OutputSection* p -> OutputSection *P by the LLVM coding style.

Please look around to make sure your new code matches with other code in the same file in style.

[shenhan]

ELF/Writer.cpp

722

Most of relro have PROGBITS, but ".dynamic" & ".tbss" don't. So the condition test is to keep those 2 sections contiguous with other relro sections.

[ruiu]

ELF/Writer.cpp

722

Doesn't that mean that the priority you gave to RF_NON_TLS_BSS_RO is not appropriate? If you give it lower priority than the RELRO priority (i.e. RF_NON_TLS_BSS_RO), it should automatically work, no?

[ruiu]

ELF/Writer.cpp

1690

Please separate this part as a separate patch, as this patch contains two unrelated changes.

[shenhan]

@espindola would you mind take a look?

[grimar]

Can you add a test case showing the difference in layout after this patch applied?

ELF/Writer.cpp

720

"ALLOC" -> SHF_ALLOC or "ALLOC" -> allocatable

725

Please be consistent. You mix ALLOC and "ALLOC". I would just use SHF_ALLOC everywhere.

[shenhan]

Thanks. Done with a test case.

[shenhan]

Any further thoughts? If not, I'll proceed to fixing all the other test failures caused by section re-arrangement.

[grimar]

ELF/Writer.cpp

728

So, this places SHT_DYNSYM and SHT_SYMTAB sections first
in "a" sections group just because they do not get RF_NOT_TLS rank
(like other "a" sections) because of this early return, right?

Then it seems that behavior is based on an accident.
I would suggest adding new RF_* rank probably to make it explicit.

test/ELF/dynsec-at-beginning.s

16

I am not sure having "aw" section is useful here.
I would instead expect to see foo as "a" section instead. To show
how non-synthetic SHF _ALLOC sections are placed with the new code.
Because currently, you show the layout of "a" synthetic sections
(.dynsym, .dynstr, .hash) only.

[grimar]

This change looks good for me (with a better name for rank).
Currently, as you know, there are 57 failing test cases.
Please fix them and update the patch.

ELF/Writer.cpp

693

RF_DYN_SYM does not seem to be a good name because
you use it for both SHT_DYNSYM and SHT_STRTAB.

I do not have an idea about the good name now. Maybe RF_ALLOC_FIRST?

[shenhan]

Fixed all affected test cases.

[grimar]

Few comments for now + please upload the patch with the context (just read the https://llvm.org/docs/Phabricator.html).

test/ELF/basic-ppc.s

15 ↗

(On Diff #144979)

Remove trailing whitespace, please.

60 ↗

(On Diff #144979)

(1) is new and excessive. The same issues below.

test/ELF/dynsec-at-beginning.s

13

.text is AX please keep the full attributes name.

[ruiu]

LGTM

[grimar]

Please update the patch with my comments addressed, I would like to review the test cases carefully.

[shenhan]

Refined test cases changes and provide more context.

[grimar]

Ok, I reviewed the changed test cases and unfortunately, now I have many concerns about this patch.
Issues I found are in comments, I think they are critical and needs fix/investigation first of all.

But I also think that given the issues observed and the fact that it makes
output different with the default output from gnu linkers,
I probably want to suggest to hide this new functionality under some -z <option> flag.

Will be happy to see the opinions of other people.

test/ELF/arm-exidx-shared.s

44 ↗

(On Diff #145041)

This calculation comment needs an update since values changed.

test/ELF/dynsec-at-beginning.s

14

Please address this comment (.text is AX, not just A)

test/ELF/linkerscript/no-space.s

4 ↗

(On Diff #145041)

I do not think this is correct, sorry. This change broke the intention of the test case I believe.

You did that because LLD starts triggering an error:

error: section .dynsym file range overlaps with foo
>>> .dynsym range is [0x1000, 0x1017]
>>> foo range is [0x1000, 0x1007]

What happens because orphan section .dynsym is placed before foo. And then during
assigning of VA, Dot is explicitly set to 0 for foo, making it intersect with .dynsym.

I think the expected behavior is to not place these orphan sections before foo, since
the position of foo is explicitly requested by linker script. And sure I do not think
we should emit an error in that case.

This case needs some investigation.
I'll be happy to hear other people opinion on that too.

test/ELF/linkerscript/out-of-order.s

3 ↗

(On Diff #145041)

The same here. I do not think you should "fix" this script. It was valid by itself. It should just work.

With the original linker script, this patch makes LLD to produce invalid output (actually no output at all as FileSize is broken).

[shenhan]

test/ELF/linkerscript/no-space.s

4 ↗

(On Diff #145041)

Thanks for pointing this out, yes, I agree we need to have consensus on this (and the "out-of-order.s" test case below).

Here is my thoughts:

1. The test writer assume the fact that "foo" must be the first section in its segment (which is a group of output sections), otherwise, its address intersects with the first output section in the segment, because DOT is set to 0 for "foo" by linkerscript.

2. There is no fact in the test case supports this assumption.

3. So this test case might cause linker error whenever output sections change relative order in the segment.

So my suggestion:
Honor the assumption, so instead of change the DOT for foo, change it for .dynsym (the first output section of segment):

• # RUN: echo "SECTIONS {foo 0 : {*(foo*)} }" > %t.script

+ # RUN: echo "SECTIONS {.dynsym 0 : {*(.dynsym)} }" > %t.script
This reserves the origin test intention.

.OR.
Always layout output sections with explicit address assignment first, then layout those without. So for this particular case, the origin output section order is:

.dynsym .dynstr foo

We layout it like below:

foo .dynsym .dynstr

.OR.
Report error on rewinding "." to a conflict address.

[This also applies to out-of-order.s test case below.]

I'm happy to go any direction.

Comments?

[grimar]

test/ELF/linkerscript/no-space.s

4 ↗

(On Diff #145041)

.OR.
Always layout output sections with explicit address assignment first

I believe it is the correct way. A script should specify the layout, any orphans
should be placed after the explicitly specified sections. That seems logically correct
and consistent with gnu linkers behavior (I think).

I would really want to hear from other people before proceeding this place probably.

[shenhan]

test/ELF/linkerscript/no-space.s

4 ↗

(On Diff #145041)

Thanks, George.

@ruiu Can you comment?

[grimar]

test/ELF/linkerscript/no-space.s

4 ↗

(On Diff #145041)

Can you update the test cases you had to change so that these sections be not the orphans (will be listed explicitly)?
Let's see if we can try to go with that change then and watch how it works in practice.

[shenhan]

Revised linkerscript/out-of-order.s and linkerscript/no-space.s to honor layout constraint (also added notes). Also addressed previous 2 minor comments.

[grimar]

Thanks for an update!

I tested check-lld both on windows and ubuntu and
there are still 6 test cases that are failing for me.
(I think that was true for previous iteration too).

50> Failing Tests (6):
50> lld :: ELF/aarch64-copy.s
50> lld :: ELF/arm-copy.s
50> lld :: ELF/map-file.s
50> lld :: ELF/relocation.s
50> lld :: ELF/version-script-extern.s
50> lld :: ELF/x86-64-retpoline-znow-linkerscript.s

My suggestions about how we should adjust the test cases are also inline.
Let's discuss if anything I am suggesting does not look OK for some reason to you.

test/ELF/linkerscript/no-space.s

10 ↗

(On Diff #145501)

.dynstr is still an orphan.

Let's just list them explicitly here:
SECTIONS {foo 0 : {*(foo*)} .dynsym : { *(.dynsym) } .dynstr : { *(.dynstr) } }

14 ↗

(On Diff #145501)

synsym -> dynsym

SECTIONS {foo : {*(foo*)} .dynsym : { *(.dynsym) } .dynstr : { *(.dynstr) } }

test/ELF/linkerscript/out-of-order.s

3 ↗

(On Diff #145041)

I do not understand why you changed .data to .dynamic actually.
What your patch changed is the order of "a" sections. That breaks the current scripts
which previously would put dynsym/dynstr correctly, but now - don't.
And I think we should adjust only that part, no need to update anything else probably.

Lets do this:
SECTIONS { .data 0x4000 : { *(.data) } .dynsym 0x2000 : { *(.dynsym ) } .dynstr : { *(.dynstr ) } }

So what changed is that we explicitly start the second segment from .dynsym instead of .text,
so that '.dynsym'/.dynstr are not an orphans now, and that allows to place it correctly. Layout is then:

1 .data         00000008 0000000000004000 DATA
2 .dynamic      00000060 0000000000004008
3 .dynsym       00000018 0000000000002000
4 .dynstr       00000001 0000000000002018
5 .text         00000008 000000000000201c TEXT DATA

[shenhan]

Updated according to review feedback. Also synced to upstream HEAD and re-run all tests. All passed now.

[shenhan]

Thanks for the review.

[grimar]

I do not know what is wrong, but the following tests are still failing for me.

30> Failing Tests (5):
30> lld :: ELF/aarch64-copy.s
30> lld :: ELF/arm-copy.s
30> lld :: ELF/note-noalloc.s
30> lld :: ELF/relocation.s
30> lld :: ELF/version-script-extern.s

note-noalloc.s is a new one, you have to update it, but others are old and I see you already updated them in the patch,
they seem to be trivial, so not sure what is wrong here, please check your configuration because I tested on 2 and result was the same.

The rest of changes looks fine to me mostly I think (I'll probably adjust few minor things after your commit).

I do not want to be a stopper for this one anymore, so please feel free to commit after fixing above tests.
And let's see how this change works in practice.

[shenhan]

Synced to newest and re-ran tests, make sure everything passes.

[shenhan]

Thanks. Landed as https://llvm.org/svn/llvm-project/lld/trunk@332038

[shenhan]

Some clarification why my test result is different from George's.

I noticed that my build tree is configured with option "-DLLVM_OPTIMIZED_TABLEGEN=On", this seemingly innocuous option changed the behavior of at least 4 cases. After I dropped these 4 options, I saw the 4 new failures, and a new CL has been submitted to fix these 4. https://reviews.llvm.org/D46730

[grimar]

In D45788#1095337, @shenhan wrote:

Some clarification why my test result is different from George's.

I noticed that my build tree is configured with option "-DLLVM_OPTIMIZED_TABLEGEN=On", this seemingly innocuous option changed the behavior of at least 4 cases. After I dropped these 4 options, I saw the 4 new failures, and a new CL has been submitted to fix these 4. https://reviews.llvm.org/D46730

FWIW, I am using -DLLVM_OPTIMIZED_TABLEGEN=1 for windows build too.

[grimar]

Sorry, but I had to revert this in r332085 "[ELF] - Revert of: r332038, r332054, r332060, r332061, r332062, r332063"

Bots were still broken. We need to find a reason for the failures.
Please, next time check the bots after commit. That is undesirable to have them broken for a long time.

Failing bots I observed were:
http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast/builds/17042
http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/29845

Now they are OK.

[mstorsjo]

In D45788#1095683, @grimar wrote:

Sorry, but I had to revert this in r332085 "[ELF] - Revert of: r332038, r332054, r332060, r332061, r332062, r332063"

Thanks for reverting, I was also scratching my head over this.

Bots were still broken. We need to find a reason for the failures.
Please, next time check the bots after commit. That is undesirable to have them broken for a long time.

Failing bots I observed were:
http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast/builds/17042
http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/29845

A couple more ones:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap/builds/5428
http://lab.llvm.org:8011/builders/clang-with-lto-ubuntu/builds/8464
http://lab.llvm.org:8011/builders/clang-lld-x86_64-2stage/builds/5405
http://lab.llvm.org:8011/builders/clang-cmake-aarch64-lld/builds/4560

[grimar]

btw, before reverting I tried check-lld locally. I had test failures too, though I had 4 when bots had 2. My guess is that something is wrong with the sorting of output sections.
Maybe stable/unstable sorting is a key to resolving the issue, I had no chance to look closer yet, I am busy with a different task right now. I'll try to take a look when finish things I am working on.

[shenhan]

Sorry for breaking the builders. Should double check again after my fix for the broken 4 cases.

I'll look into the unstableness of output section sorting.

[shenhan]

Merge D46764 (Fix test cases that check addresses that are not always invariable) into this.

Also address Peter Smith's comments.

[grimar]

All tests pass for me now. LGTM, thanks!

[NickHung]

test/ELF/linkerscript/addr-zero.test

11 ↗

(On Diff #146868)

This change breaks the value of foo.
The expected value of foo is 0x0.

[grimar]

test/ELF/linkerscript/addr-zero.test

11 ↗

(On Diff #146868)

I think the script should be just changed to

foo = ADDR(.dynsym) - ABSOLUTE(ADDR(.dynsym));

where .dynsym is the first section now.

The problem with this script seems to be that it tries to evaluate ABSOLUTE value for .text
too early. When we assign to foo we do not yet know the absolute address of the .text.

Before this patch, .text was the first section at VA = 0, so this just worked.
Such script would not produce zero value for foo with any other
section other than .text I believe.

I am not sure (and did not find) what was the initial intention to support script like this.
Perhaps there was some other issue which produced some broken value instead of zero.

ELF/Writer.cpp

enum RankFlags {
   RF_EXEC = 1 << 12,
   RF_NON_TLS_BSS = 1 << 11,
   RF_NON_TLS_BSS_RO = 1 << 10,
   RF_NOT_TLS = 1 << 9,
   RF_BSS = 1 << 8,
   RF_NOTE = 1 << 7,
   RF_PPC_NOT_TOCBSS = 1 << 6,
   RF_PPC_OPD = 1 << 5,
   RF_PPC_TOCL = 1 << 4,
   RF_PPC_TOC = 1 << 3,
   RF_PPC_BRANCH_LT = 1 << 2,
   RF_MIPS_GPREL = 1 << 1,
   RF_MIPS_NOT_GOT = 1 << 0
 };
 
 static unsigned getSectionRank(const OutputSection *Sec) {
   unsigned Rank = 0;
if (Sec->Name == ".interp")
     return Rank;
   Rank |= RF_NOT_INTERP;
 
   // Allocatable sections go first to reduce the total PT_LOAD size and
   // so debug info doesn't change addresses in actual code.
   if (!(Sec->Flags & SHF_ALLOC))
     return Rank | RF_NOT_ALLOC;
 
+  // Place .dynsym and .dynstr at the beginning of SHF_ALLOC
+  // sections. We want to do this to mitigate the possibility that
+  // huge .dynsym and .dynstr sections placed between text sections
+  // cause relocation overflow.  Note: .dynstr has SHT_STRTAB type and
+  // SHF_ALLOC attribute, whereas sections that only have SHT_STRTAB
+  // but without SHF_ALLOC is placed at the end. All "Sec" reaching
+  // here has SHF_ALLOC bit set.
+  if (Sec->Type == SHT_DYNSYM || Sec->Type == SHT_STRTAB)
+    return Rank;
+
   // Sort sections based on their access permission in the following
   // order: R, RX, RWX, RW.  This order is based on the following
   // considerations:
   // * Read-only sections come first such that they go in the
   //   PT_LOAD covering the program headers at the start of the file.
   // * Read-only, executable sections come next, unless the
   //   -no-rosegment option is used.
   // * Writable, executable sections follow such that .plt on
template <class ELFT> void Writer<ELFT>::finalizeSections() {
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.
   for (OutputSection *Sec : OutputSections)
     Sec->finalize<ELFT>();
 }
 
 // The linker is expected to define SECNAME_start and SECNAME_end
 // symbols for a few sections. This function defines them.
 template <class ELFT> void Writer<ELFT>::addStartEndSymbols() {
   auto Define = [&](StringRef Start, StringRef End, OutputSection *OS) {
     // These symbols resolve to the image base if the section does not exist.
     // A special value -1 indicates end of the section.
     if (OS) {
       addOptionalRegular(Start, OS, 0);
       addOptionalRegular(End, OS, -1);
     } else {
       if (Config->Pic)
         OS = Out::ElfHeader;
       addOptionalRegular(Start, OS, 0);
       addOptionalRegular(End, OS, 0);
     }
   };
 
   Define("__preinit_array_start", "__preinit_array_end", Out::PreinitArray);

test/ELF/aarch64-copy.s

 // Page(S + A) - Page(P) = 0x40000 - 0x20000 = 0x20000 = 131072
 // CODE-NEXT:  20004: {{.*}} adrp x2, #131072
 // S(y) = 0x40010, A = 0
 // (S + A) & 0xFFF = 0x10 = 16
 // CODE-NEXT:  20008: {{.*}} add  x2, x2, #16
 
 // RODATA: Contents of section .rodata:
 // S(z) = 0x40014
-// RODATA-NEXT:  101c8 14000400
+// RODATA-NEXT:  10228 14000400

test/ELF/arm-copy.s

 // ((S + A) & 0xffff0000) >> 16 = 0x1
 // CODE-NEXT:   11004:       01 20 40 e3    movt    r2, #1
 // CODE-NEXT:   11008:       04 30 9f e5    ldr     r3, [pc, #4]
 // CODE-NEXT:   1100c:       00 30 93 e5    ldr     r3, [r3]
 
 
 // RODATA: Contents of section .rodata:
 // S(z) = 0x13004
-// RODATA-NEXT: 10114 04300100
+// RODATA-NEXT: 10144 04300100

test/ELF/dynsec-at-beginning.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t
+
+# RUN: ld.lld --hash-style=gnu -o %t1  %t -shared
+# RUN: llvm-readobj -elf-output-style=GNU -s %t1 | FileCheck %s
+
+# Dynamic symbol and dynamic strtab sections are at the beginning of
+# SHF_ALLOC sections.
+# CHECK:      .dynsym  {{.*}}   A
+# CHECK-NEXT: .dynstr  {{.*}}   A
+# CHECK-NEXT: .hash    {{.*}}   A
+# CHECK-NEXT: .text    {{.*}}   AX
+# CHECK-NEXT: foo      {{.*}}   WA
+
+.section foo, "aw"
+.byte 0