[ELF] Sort notes by alignment in decreasing order

[phosek]

Summary

This change implements the solution to PR41000 proposed in the bug
by sorting notes by alignment in decreasing order to close the gap
that might occur when notes use different alignments and to ensure
that PT_NOTE is packed correctly.

[jakehehrlich]

Would be nice to have a test where 2 sections are out of order, and this change puts them into the correct order. It's not clear from this if the build ID section is naturally placed at the end or not.

[phosek]

In D59120#1422341, @jakehehrlich wrote:

Would be nice to have a test where 2 sections are out of order, and this change puts them into the correct order. It's not clear from this if the build ID section is naturally placed at the end or not.

The build ID test already does the re-ordering so it acts as a test, but I can also make another one if you prefer.

[pcc]

An alternative solution might be to create a PT_NOTE for each note upfront, and opportunistically merge them if they end up being laid out contiguously. This would also handle the case where a note's size is not a multiple of its alignment.

[MaskRay]

Peter's suggestion resembles the approach taken by ld.bfd: it can create multiple PT_NOTE segments. I also favor this.

[xiangzhangllvm]

if just .note.gnu.property require 64-bit alignment, I think it time to change the alignment of this section.

I think we need change the .note.gnu.property section alignment to 4-byte in Clang-TableGen, because all its element is 4-byte required now. 
The old ABI required some of note.gnu.property' elements be 8-byte aligned in 64-bit machine, so the section required 8-byte alignment.
Last year, I found a bug about this alignment between GCC and CLANG, Then I discussed with the ABI designer and changed its element's alignment in https://reviews.llvm.org/D56080 .
I think there are already no ‘significance’ of 8 byte alignment for this section, we can change it now in LLVM.

[peter.smith]

I personally favour a separate PT_NOTE section per alignment, that gives a note parser simple rule to iterate through the section (the p_align field). I think ordering by decreasing alignment will work in practice for the note sections that we have now, but it may not be in the future. I also think that this is worth doing even if clang is changed to generate .note.gnu.property sections that are 4-byte aligned; clang will often use libraries compiled by gcc (or some other compiler) that does use 8-byte aligned sections.

There is a long glibc thread that covers a similar discussion in the gnu community https://sourceware.org/ml/libc-alpha/2018-08/msg00340.html , it is quite long so I've pulled out a few bits of it here:

• https://sourceware.org/ml/libc-alpha/2018-08/msg00344.html and follow-up https://sourceware.org/ml/libc-alpha/2018-08/msg00347.html on why two separate PT_NOTE sections were needed.
• https://sourceware.org/ml/libc-alpha/2018-08/msg00468.html rejection of changing ld bfd to that of gold and just setting the alignment of .gnu.property to 4-bytes. Ostensibly due to presence of large number of binaries with 8-byte aligned sections.

From what I can tell:

• ld.bfd outputs a separate PT_NOTE per p_align.
• ld.gold ignores the 8-byte alignment of the .note.gnu.property in the input object and changes it to 4 so that only one PT_NOTE is required.
• glibc works for both, given that .note.gnu.property doesn't strictly need 8 byte alignment.

[MaskRay]

ld.bfd outputs a separate PT_NOTE per p_align.

No, it merges adjacent SHT_NOTE in some circumstances. The rule is complicated, though.

We can place adjacent SHT_NOTE|SHF_ALLOC sections with the same section alignment into the same PT_NOTE segment, as what the ld.bfd patch does
https://sourceware.org/git/?p=binutils-gdb.git;a=blobdiff;f=bfd/elf.c;h=8850efe20e9ea5c9f59bac839cf453790594b6af;hp=5320ae2237fcb67e39c7fd9f47a8ce81338d2aa1;hb=23e463ed7c0d289e2291aaefd576bf02efd98df8;hpb=e66cfcef729d758a5e605d57600530ad9b1bb9c3

I'm not sure if a separate PT_NOTE section per alignment would work for all cases. I don't think the size of a note section with 8-byte alignment is guaranteed to be a multiple of 8 byte.

I believe valid SHF_NOTE sections are either 4-byte or 8-byte aligned and the size is guaranteed to be a multiple of its section alignment. The input is broken if it isn't. It doesn't look wrong for me if lld produces a PT_NOTE that cannot be parsed by ld.so or other tools. Such check may still be nice to have, though.

.section .note.a, "a", @note
.p2align 2
.space 1

.section .note.b, "a", @note
.p2align 2
.space 2

In this example, .note.a's size is not aligned but ld.bfd places .note.a .note.b in the same PT_NOTE segment.

[ruiu]

At this point I'm wonder if we can simply emit one PT_NOTE for each .note section. Guys, what do you think?

[MaskRay]

Both choices look good to me:

• emit one PT_NOTE for each SHF_ALLOC .note*
• emit one PT_NOTE for adjacent SHF_ALLOC .note* with the same alignment (don't check alignment of their sizes)

[peter.smith]

In D59120#1428640, @MaskRay wrote:

Both choices look good to me:

• emit one PT_NOTE for each SHF_ALLOC .note*
• emit one PT_NOTE for adjacent SHF_ALLOC .note* with the same alignment (don't check alignment of their sizes)

I agree. I think either of those options will work.

[phosek]

Superseded by D59531.

lld/ELF/Writer.cpp

static bool compareSections(const BaseCommand *ACmd, const BaseCommand *BCmd) {
   const OutputSection *B = cast<OutputSection>(BCmd);
 
   if (A->SortRank != B->SortRank)
     return A->SortRank < B->SortRank;
 
   if (!(A->SortRank & RF_NOT_ADDR_SET))
     return Config->SectionStartMap.lookup(A->Name) <
            Config->SectionStartMap.lookup(B->Name);
+
+  if (A->Type == SHT_NOTE && B->Type == SHT_NOTE)
+    return A->Alignment > B->Alignment;
+
   return false;
 }
 
 void PhdrEntry::add(OutputSection *Sec) {
   LastSec = Sec;
   if (!FirstSec)
     FirstSec = Sec;
   p_align = std::max(p_align, Sec->Alignment);

lld/test/ELF/build-id.s

 # ALIGN-NEXT:   SHF_ALLOC
 # ALIGN-NEXT: ]
 # ALIGN-NEXT: Address:
 # ALIGN-NEXT: Offset: [[_:0x[0-9A-Z]*(0|4|8|C)$]]
 # ALIGN-NEXT: Size:
 # ALIGN-NEXT: Link:
 # ALIGN-NEXT: Info:
 # ALIGN-NEXT: AddressAlignment: 4
+# ALIGN:      Name: .note.test
+# ALIGN-NEXT: Type: SHT_NOTE
+# ALIGN-NEXT: Flags [
+# ALIGN-NEXT:   SHF_ALLOC
+# ALIGN-NEXT: ]
+# ALIGN-NEXT: Address:
+# ALIGN-NEXT: Offset:
+# ALIGN-NEXT: Size:
+# ALIGN-NEXT: Link:
+# ALIGN-NEXT: Info:
+# ALIGN-NEXT: AddressAlignment: 1
 
-# DEFAULT:      Contents of section .note.test:
 # DEFAULT:      Contents of section .note.gnu.build-id:
 # DEFAULT-NEXT: 04000000 08000000 03000000 474e5500  ............GNU.
-# DEFAULT-NEXT: 894c04e8 fbf5556b
+# DEFAULT-NEXT: a8559a18 b5591183
+# DEFAULT:      Contents of section .note.test:
 
 # MD5:      Contents of section .note.gnu.build-id:
 # MD5-NEXT: 04000000 10000000 03000000 474e5500  ............GNU.
-# MD5-NEXT: 6a51bbd7 9e8ee3f9 2e02d213 711cfec9
+# MD5-NEXT: aba082ff 066f94ce 66e40824 df7a3f60
 
 # SHA1:      Contents of section .note.gnu.build-id:
 # SHA1-NEXT: 04000000 14000000 03000000 474e5500  ............GNU.
-# SHA1-NEXT: 9a8618b1 d6fd0e5c eda73dd8 76de5596
+# SHA1-NEXT: c47692ed 095f88fc f9a08777 aa1bc6de
 
 # UUID:      Contents of section .note.gnu.build-id:
 # UUID-NEXT: 04000000 10000000 03000000 474e5500  ............GNU.
 
 # HEX:      Contents of section .note.gnu.build-id:
 # HEX-NEXT: 04000000 04000000 03000000 474e5500  ............GNU.
 # HEX-NEXT: 12345678
 
 # NONE-NOT: Contents of section .note.gnu.build-id: