[ELF] Allow placing non-string SHF_MERGE sections with different alignments into the same MergeSyntheticSection

[MaskRay]

Summary

The difference from D63432/r365015 is that this patch does not place
SHF_STRINGS sections with different alignments into the same
MergeSyntheticSection. That would:

(1) create unnecessary padding and thus waste space
(2) create unaligned sections when tail merge (-O2) is enabled.

The alignment of MergeTailAlignment::Builder was out of sync in D63432.
MOVAPS on such unaligned strings can raise SIGSEGV.

This should fix PR42289: the Linux kernel has a use case that input
files have .rodata.cst32 sections with different alignments. The
expectation (and what ld.bfd and gold do) is that in the -r link, there
is only one .rodata.cst32 (SHF_MERGE sections with different alignments
can be combined), but lld currently creates one for each different
alignment.

The current merging strategy:

1. Group SHF_MERGE sections by (name, sh_flags, sh_entsize and sh_addralign). String merging is performed among a group, even if -O0 is specified.
2. Create one output section for each group. This is a special case in addInputSec().

This patch changes 1) to:

1. Group SHF_MERGE sections by (name, sh_flags, sh_entsize). String merging is performed among a group, even if -O0 is specified.

We will thus create just one .rodata.cst32 . This also improves merging
efficiency when sections with the same name but different alignments are
combined.

[MaskRay]

Add nickdesaulniers

[MaskRay]

That would (1) waste space and (2) create unaligned sections when tail merge (-O2) is enabled. MOVAPS on such unaligned strings can raise SIGSEGV.

I haven't figured out the root cause of (2) yet.

(1) justifies a change, otherwise we will get something like a.......b.......c......., which wastes space.

[peter.smith]

In D64200#1570169, @MaskRay wrote:

That would (1) waste space and (2) create unaligned sections when tail merge (-O2) is enabled. MOVAPS on such unaligned strings can raise SIGSEGV.

I haven't figured out the root cause of (2) yet.

(1) justifies a change, otherwise we will get something like a.......b.......c......., which wastes space.

I hadn't realised that the change would also affect SHF_STRINGS sections as well, IIRC sh_entsize means the size of the character so it can make sense for the alignment to be higher than the sh_entsize. This is bringing back memories. Many years ago we had a similar problem mixing objects from Arm's proprietary compiler and arm-none-eabi-gcc. The ARM compiler only used SHF_STRINGS with sh_align 1 with the code using byte by byte accesses to those strings. In arm-none-eabi-gcc the SHF_STRINGS has sh_align 4 and copied strings using words instead of bytes. Within the SHF_STRINGS section the strings were padded to a 4-byte boundary. On the ARM processors of the time didn't support unaligned accesses so when the strings were merged without taking into account alignment padding the resulting binary crashed.

In that particular case we permitted strings from an equal to or lower alignment to be merged, but not a higher to a lower alignment. Within that higher aligned string section we needed to maintain alignment padding to ensure each string started at an aligned boundary. This might be more difficult to do in LLD.

I think for now excluding SHF_STRINGS from different alignment merging is the right thing to do. If we want to enable it we'll need to ensure each string starts on a correctly aligned boundary to ensure correctness.

[davezarzycki]

I just did a quick test of this patch and now stage two testing works (Fedora 30, x86-64)

[MaskRay]

Update description

The root cause is clear now.

MergeTailSection::MergeTailSection(StringRef Name, uint32_t Type,
                                   uint64_t Flags, uint32_t Alignment)
    : MergeSyntheticSection(Name, Type, Flags, Alignment),
      Builder(StringTableBuilder::RAW, Alignment) {}

Builder::Alignment was out of sync if we update MergeTailSection::Alignment.

[MaskRay]

In D64200#1570259, @peter.smith wrote:

In D64200#1570169, @MaskRay wrote:

That would (1) waste space and (2) create unaligned sections when tail merge (-O2) is enabled. MOVAPS on such unaligned strings can raise SIGSEGV.

I haven't figured out the root cause of (2) yet.

(1) justifies a change, otherwise we will get something like a.......b.......c......., which wastes space.

I hadn't realised that the change would also affect SHF_STRINGS sections as well, IIRC sh_entsize means the size of the character so it can make sense for the alignment to be higher than the sh_entsize. This is bringing back memories. Many years ago we had a similar problem mixing objects from Arm's proprietary compiler and arm-none-eabi-gcc. The ARM compiler only used SHF_STRINGS with sh_align 1 with the code using byte by byte accesses to those strings. In arm-none-eabi-gcc the SHF_STRINGS has sh_align 4 and copied strings using words instead of bytes. Within the SHF_STRINGS section the strings were padded to a 4-byte boundary. On the ARM processors of the time didn't support unaligned accesses so when the strings were merged without taking into account alignment padding the resulting binary crashed.

D63432 had the very issue. A MergeTailSection was created with alignment 1. In its ctor the StringTableBuilder was initialized with alignment 1. Then, the MergeTailSection's alignment was updated to 16 but StringTableBuilder::Alignment was not updated. StringTableBuilder actually can handle strings with alignment greater than 1 (though some strings may not be mergeable, e.g. "abc" and "bc" can be merged if sh_addralign is 1 but can't if sh_addralign is 2).

In that particular case we permitted strings from an equal to or lower alignment to be merged, but not a higher to a lower alignment. Within that higher aligned string section we needed to maintain alignment padding to ensure each string started at an aligned boundary. This might be more difficult to do in LLD.

Agreed.

I think for now excluding SHF_STRINGS from different alignment merging is the right thing to do. If we want to enable it we'll need to ensure each string starts on a correctly aligned boundary to ensure correctness.

I agree. tail-merge-string-align2.s demonstrates that different alignments on SHF_STRINGS can create too much padding.

@davezarzycki Thank you for testing!

[peter.smith]

Based on the closeness to D63432 and Dave's testing LGTM.

ELF/SyntheticSections.cpp

 
 template <class ELFT> bool VersionNeedSection<ELFT>::isNeeded() const {
   return SharedFile::VernauxNum != 0;
 }
 
 void MergeSyntheticSection::addSection(MergeInputSection *MS) {
   MS->Parent = this;
   Sections.push_back(MS);
+  assert(Alignment == MS->Alignment || !(MS->Flags & SHF_STRINGS));
+  Alignment = std::max(Alignment, MS->Alignment);
 }
 
 MergeTailSection::MergeTailSection(StringRef Name, uint32_t Type,
                                    uint64_t Flags, uint32_t Alignment)
     : MergeSyntheticSection(Name, Type, Flags, Alignment),
       Builder(StringTableBuilder::RAW, Alignment) {}
 
 size_t MergeTailSection::getSize() const { return Builder.getSize(); }
auto I = llvm::find_if(MergeSections, [=](MergeSyntheticSection *Sec) {
       // While we could create a single synthetic section for two different
       // values of Entsize, it is better to take Entsize into consideration.
       //
       // With a single synthetic section no two pieces with different Entsize
       // could be equal, so we may as well have two sections.
       //
       // Using Entsize in here also allows us to propagate it to the synthetic
       // section.
+      //
+      // SHF_STRINGS section with different alignments should not be merged.
       return Sec->Name == OutsecName && Sec->Flags == MS->Flags &&
-             Sec->Entsize == MS->Entsize && Sec->Alignment == MS->Alignment;
+             Sec->Entsize == MS->Entsize &&
+             (Sec->Alignment == MS->Alignment || !(Sec->Flags & SHF_STRINGS));
     });
     if (I == MergeSections.end()) {
       MergeSyntheticSection *Syn =
           createMergeSynthetic(OutsecName, MS->Type, MS->Flags, MS->Alignment);
       MergeSections.push_back(Syn);
       I = std::prev(MergeSections.end());
       S = Syn;
       Syn->Entsize = MS->Entsize;

test/ELF/merge-align2.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+
+# RUN: ld.lld %t.o -o %t
+# RUN: llvm-readelf -S %t | FileCheck --check-prefix=SEC %s
+# RUN: llvm-readelf -x .cst8 %t | FileCheck %s
+
+# RUN: ld.lld -O0 -r %t.o -o %t1.o
+# RUN: llvm-readelf -S %t1.o | FileCheck --check-prefix=SEC %s
+# RUN: llvm-readelf -x .cst8 %t1.o | FileCheck %s
+
+## Check that if we have SHF_MERGE sections with the same name, flags and
+## entsize, but different alignments, we combine them with the maximum input
+## alignment as the output alignment.
+
+# SEC: Name  Type     {{.*}} Size   ES Flg Lk Inf Al
+# SEC: .cst8 PROGBITS {{.*}} 000018 08  AM  0   0  8
+
+# CHECK:      0x{{[0-9a-f]+}} 02000000 00000000 01000000 00000000
+# CHECK-NEXT: 0x{{[0-9a-f]+}} 03000000 00000000
+
+.section .cst8,"aM",@progbits,8,unique,0
+.align 4
+.quad 1
+.quad 1
+
+.section .cst8,"aM",@progbits,8,unique,1
+.align 4
+.quad 1
+.quad 2
+
+.section .cst8,"aM",@progbits,8,unique,2
+.align 8
+.quad 1
+.quad 3

test/ELF/merge-entsize2.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+
+# RUN: ld.lld %t.o -o %t
+# RUN: llvm-readelf -S %t | FileCheck --check-prefix=SEC %s
+# RUN: llvm-readelf -x .cst %t | FileCheck --check-prefix=HEX %s
+
+# RUN: ld.lld -O0 -r %t.o -o %t1.o
+# RUN: llvm-readelf -S %t1.o | FileCheck --check-prefix=SEC-R %s
+# RUN: llvm-readelf -x .cst %t1.o | FileCheck --check-prefix=HEX-R %s
+
+## Check that SHF_MERGE sections with the same name, sh_flags and sh_entsize
+## are grouped together and can be merged within the group.
+
+## .cst 0 and .cst 1 are merged (sh_entsize=4). The result and .cst 2 and
+## combined (sh_entsize=8). The output sh_entsize is 0.
+# SEC:   Name  Type     {{.*}} Size   ES Flg Lk Inf Al
+# SEC:   .cst  PROGBITS {{.*}} 000020 00  AM  0   0  8
+
+## .cst 0 and .cst 1 are merged, but emitted as a separate output section.
+# SEC-R: .cst  PROGBITS {{.*}} 00000c 04  AM  0   0  4
+# SEC-R: .cst  PROGBITS {{.*}} 000010 08  AM  0   0  8
+
+# HEX:      Hex dump of section '.cst':
+# HEX-NEXT: 0x{{[0-9a-f]+}} 01000000 00000000 02000000 00000000
+# HEX-NEXT: 0x{{[0-9a-f]+}} 01000000 00000000 03000000 00000000
+
+# HEX-R:      Hex dump of section '.cst':
+# HEX-R-NEXT: 0x00000000 01000000 00000000 02000000
+# HEX-R-EMPTY:
+# HEX-R-NEXT: Hex dump of section '.cst':
+# HEX-R-NEXT: 0x00000000 01000000 00000000 03000000 00000000
+
+.section .cst,"aM",@progbits,4,unique,0
+.align 2
+.long 1
+.long 0
+.long 2
+
+.section .cst,"aM",@progbits,4,unique,1
+.align 4
+.long 1
+.long 0
+.long 2
+
+.section .cst,"aM",@progbits,8,unique,2
+.align 8
+.quad 1
+.quad 3

test/ELF/merge-reloc-O0.s

-# REQUIRES: x86
-# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
-# RUN: ld.lld %t.o -r -o %t2.o -O0
-# RUN: llvm-readobj -S --section-data %t2.o | FileCheck %s
-
-# We combine just the sections with the same name and sh_entsize.
-
-# CHECK:      Name: .foo
-# CHECK-NEXT: Type: SHT_PROGBITS
-# CHECK-NEXT: Flags [
-# CHECK-NEXT:   SHF_ALLOC
-# CHECK-NEXT:   SHF_MERGE
-# CHECK-NEXT: ]
-# CHECK-NEXT: Address:
-# CHECK-NEXT: Offset:
-# CHECK-NEXT: Size: 16
-# CHECK-NEXT: Link:
-# CHECK-NEXT: Info:
-# CHECK-NEXT: AddressAlignment: 1
-# CHECK-NEXT: EntrySize: 8
-# CHECK-NEXT: SectionData (
-# CHECK-NEXT:   0000: 41000000 00000000 42000000 00000000
-# CHECK-NEXT: )
-
-# CHECK:      Name: .foo
-# CHECK-NEXT: Type: SHT_PROGBITS
-# CHECK-NEXT: Flags [
-# CHECK-NEXT:   SHF_ALLOC
-# CHECK-NEXT:   SHF_MERGE
-# CHECK-NEXT: ]
-# CHECK-NEXT: Address:
-# CHECK-NEXT: Offset:
-# CHECK-NEXT: Size: 8
-# CHECK-NEXT: Link:
-# CHECK-NEXT: Info:
-# CHECK-NEXT: AddressAlignment: 1
-# CHECK-NEXT: EntrySize: 4
-# CHECK-NEXT: SectionData (
-# CHECK-NEXT:   0000: 41000000 42000000
-# CHECK-NEXT: )
-
-        .section .foo, "aM",@progbits,8,unique,0
-        .quad 0x41
-        .section .foo, "aM",@progbits,8,unique,1
-        .quad 0x42
-        .section .foo, "aM",@progbits,4,unique,2
-        .long 0x41
-        .long 0x42

test/ELF/tail-merge-string-align2.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+
+# RUN: ld.lld %t.o -o %t
+# RUN: llvm-readelf -S %t | FileCheck --check-prefix=SEC %s
+# RUN: llvm-readelf -x .rodata %t | FileCheck %s
+
+# SEC: Name    Type     {{.*}} Size   ES Flg Lk Inf Al
+# SEC: .rodata PROGBITS {{.*}} 000006 01 AMS  0   0  8
+
+# CHECK: a.b.c.
+
+.section .rodata.str1.8,"aMS",@progbits,1
+.align 8
+.asciz "a"
+
+.section .rodata.str1.2,"aMS",@progbits,1
+.align 2
+.asciz "b"
+
+.section .rodata.str1.1,"aMS",@progbits,1
+.align 1
+.asciz "c"