[ELF] Produce multiple PT_NOTE segments as needed

[jakehehrlich]

Summary

Right now note sections that are next to each other are put into the same. PT_NOTE program header. This produces an issue when alignments are not accounted for. This change produces exactly one PT_NOTE per SHT_NOTE section.

See https://reviews.llvm.org/D59120 and the email thread for associated discussion. The long and short of it is that we have to have more than one PT_NOTE segment to account for alignment of headers. This change maintains order while adding as few headers as is required (unless I got my math wrong) but we could yet further reduce the number of segments by sorting the OutputSections in order of decreasing alignment (as I proposed before but was shown to be wrong as a complete solution).

[pcc]

Is it possible for this to fail with a linker script that looks like:

SECTIONS {
  . = SIZEOF_HEADERS;
  .note1 : { *(.note1) }
  . = 0x10000;
  .note2 : { *(.note2) }
}

?

[peter.smith]

In D59531#1434312, @pcc wrote:

Is it possible for this to fail with a linker script that looks like:

SECTIONS {
  . = SIZEOF_HEADERS;
  .note1 : { *(.note1) }
  . = 0x10000;
  .note2 : { *(.note2) }
}

?

AFAICT this will produce a single very large PT_NOTE. In this particular case I'd think that the intention of the script author would be for the notes to be separate as they wouldn't be accounting for the gap in the middle. Given that a parser will want to iterate based on the alignment of the program header, perhaps generate a new PT_NOTE if there is more than one alignment padding's gap between contiguous Note OutputSections.

[ruiu]

In D59531#1434312, @pcc wrote:

Is it possible for this to fail with a linker script that looks like:

SECTIONS {
  . = SIZEOF_HEADERS;
  .note1 : { *(.note1) }
  . = 0x10000;
  .note2 : { *(.note2) }
}

?

Is this realistic? I'm not worried too much about this because it seems you are intentionally creating a large gap between .note sections.

[jakehehrlich]

I think pcc's case is valid and we should be able to update the script to account for it (I think anyway). This issue arises when the offset/vaddr of the output section is already known to be larger than gap that note traversal would assume. My current algorithm makes assumptions about how section layout occurs.

Is the vaddr/offset of the output section already decided at this point? If so we can simplify this code *and* account for pcc's case. I was attempting to avoid causing this code to depend on section offsets already being decided when I wrote this.

If we can't know section vaddr/offsets at this point then I vote we fallback to just one PT_NOTE per SHT_NOTE section as was already discussed. It's not ideal but I don't see a way to support pcc's case without knowing either the vaddr of the note or the offset. Assuming all notes go into the same PT_LOAD using offset should be just as good as using vaddr.

[pcc]

In D59531#1434812, @ruiu wrote:

In D59531#1434312, @pcc wrote:

Is it possible for this to fail with a linker script that looks like:

SECTIONS {
  . = SIZEOF_HEADERS;
  .note1 : { *(.note1) }
  . = 0x10000;
  .note2 : { *(.note2) }
}

?

Is this realistic? I'm not worried too much about this because it seems you are intentionally creating a large gap between .note sections.

I suppose not. I guess a slightly more realistic case is where one of the notes appears in the linker script and another gets placed next to it as an orphan section. I'm not sure if that could actually result in a gap being created, though.

In D59531#1435362, @jakehehrlich wrote:

I think pcc's case is valid and we should be able to update the script to account for it (I think anyway). This issue arises when the offset/vaddr of the output section is already known to be larger than gap that note traversal would assume. My current algorithm makes assumptions about how section layout occurs.

Is the vaddr/offset of the output section already decided at this point? If so we can simplify this code *and* account for pcc's case. I was attempting to avoid causing this code to depend on section offsets already being decided when I wrote this.

If we can't know section vaddr/offsets at this point then I vote we fallback to just one PT_NOTE per SHT_NOTE section as was already discussed. It's not ideal but I don't see a way to support pcc's case without knowing either the vaddr of the note or the offset. Assuming all notes go into the same PT_LOAD using offset should be just as good as using vaddr.

We don't know addresses at this point, and indeed we can't because the layout of the rest of the output file depends on how many program headers there are, which is decided by this function. I would be in favour of the one PT_NOTE per SHT_NOTE as it is simpler and handles more cases.

[jakehehrlich]

We don't know addresses at this point, and indeed we can't because the layout of the rest of the output file depends on how many program headers there are, which is decided by this function.

Yep I think the only correct solution then is to use one PT_NOTE per note section then. That's kind of a shame but I think all other behaviors have a counter example (academic or otherwise). We can't relay on vaddrs and there aren't any assumptions we can make about what the relative properties between the final vaddrs will be either because of linker scripts. One per is the only solution resistant to academic counter examples (that I personally think we should take seriously).

[jakehehrlich]

Use one PT_NOTE per SHT_NOTE now instead of trying to minimize the number by assuming the layout algorithm. Changed tests to match this reality.

[ruiu]

I actually like this approach. It's much simpler, easier to understand, and perhaps easier to parse by program. I'd wait for a few days for those who don't like this approach, but if no one oppose, I'll approve. Please ping me after a few days.

[pcc]

lld/ELF/Writer.cpp

2059–2060

This comment is no longer accurate.

[MaskRay]

We don't know addresses at this point, and indeed we can't because the layout of the rest of the output file depends on how many program headers there are, which is decided by this function. I would be in favour of the one PT_NOTE per SHT_NOTE as it is simpler and handles more cases.

I also prefer one PT_NOTE per SHT_NOTE given that addresses haven't been finalized yet.

[grimar]

Looks OK for me too.

lld/test/ELF/multiple-notes.s

20 ↗

(On Diff #191422)

a PT_NOTE I guess?

[jhenderson]

lld/test/ELF/multiple-notes.s

4 ↗

(On Diff #191422)

It might be nice to use llvm-readelf --section-mapping here too to show that each section is inside the corresponding segment.

[jakehehrlich]

Roland pointed out that this will be a regression after those special high alignment notes are flushed from the ecosystem (this is apparently a recent addition and the issue will be resolved in the months to come). A possibility is that if we see a note section with greater than 4-byte alignment then we use this method but otherwise fallback to the old method. This means that on Linux binaries for the time being (while this new ABI thing is being flushed out of the ecosystem) will be slightly larger but as soon as its fixed ld.lld will be back to fully functioning. This is a general strategy too because no matter size the notes are, the reader will bump by 4-byte alignment. That seems fine to me and I'll upload that change today hopefully.

[MaskRay]

In D59531#1439899, @jakehehrlich wrote:

Roland pointed out that this will be a regression after those special high alignment notes are flushed from the ecosystem (this is apparently a recent addition and the issue will be resolved in the months to come). A possibility is that if we see a note section with greater than 4-byte alignment then we use this method but otherwise fallback to the old method. This means that on Linux binaries for the time being (while this new ABI thing is being flushed out of the ecosystem) will be slightly larger but as soon as its fixed ld.lld will be back to fully functioning. This is a general strategy too because no matter size the notes are, the reader will bump by 4-byte alignment. That seems fine to me and I'll upload that change today hopefully.

Can you ask Roland how valid it is for a SHT_NOTE section to have sh_size%sh_align != 0? If the scenario isn't realistic, can we just merge adjacent SHF_ALLOC SHT_NOTE with the same sh_align? If there is one, I believe ld.bfd and gold (binutils-gdb trunk) can create PT_NOTE segments with unparsable padding.

[jakehehrlich]

Added Roland's proposed fix

[jakehehrlich]

In D59531#1440434, @MaskRay wrote:

Can you ask Roland how valid it is for a SHT_NOTE section to have sh_size%sh_align != 0? If the scenario isn't realistic, can we just merge adjacent SHF_ALLOC SHT_NOTE with the same sh_align? If there is one, I believe ld.bfd and gold (binutils-gdb trunk) can create PT_NOTE segments with unparsable padding.

He says there is no precedent or requirement for such a thing and no reason to add such a requirement. Notes are assumed by linkers to have alignment of 4. Roland thinks both produce some unparsable PT_NOTE segments but only in the case where alignment isn't 4 or 8.

[ruiu]

Hmm, if some tools are setting a large alignment (greater than 4) to a .note section by mistake, then we probably should ignore them and treat them as a 4 byte alignment rather than respecting a wrong value. That means always setting alignment of 4 to every .note input section.

[grimar]

In D59531#1445429, @ruiu wrote:

Hmm, if some tools are setting a large alignment (greater than 4) to a .note section by mistake, then we probably should ignore them and treat them as a 4 byte alignment rather than respecting a wrong value. That means always setting alignment of 4 to every .note input section.

Sounds a bit hacky IMO. I would expect from linker to make as fewer assumptions as possible.

I.e. if some tool "setting a large alignment (greater than 4) to a .note section by mistake",
I would expect we would at least report a warning before adjusting the alignment?
And ideally the tool needs to be fixed and we then will remove that temporary workaround from the linker after some time.

[peter.smith]

In D59531#1435577, @jakehehrlich wrote:

We don't know addresses at this point, and indeed we can't because the layout of the rest of the output file depends on how many program headers there are, which is decided by this function.

Yep I think the only correct solution then is to use one PT_NOTE per note section then. That's kind of a shame but I think all other behaviors have a counter example (academic or otherwise). We can't relay on vaddrs and there aren't any assumptions we can make about what the relative properties between the final vaddrs will be either because of linker scripts. One per is the only solution resistant to academic counter examples (that I personally think we should take seriously).

If I've understood the latest patch right then pcc's original test case will still fail if both notes sections in the example below are 4-byte aligned.

SECTIONS {
  . = SIZEOF_HEADERS;
  .note1 : { *(.note1) }
  . = 0x10000;
  .note2 : { *(.note2) }
}

If this is still the intention to support this case then it would be good to add a test case.

lld/ELF/Writer.cpp

2057

Would OneProgramHeaderPerNoteSection , or MultiNoteSegmentLayout be more descriptive? Which one is more simple is a bit subjective, and means having to read the comment or code to work out what it means in practice.

2059

This is setting UseSimpleNoteLayout if any OutputSection has an alignment > 4. Was that what you intended? I was expecting only SHT_NOTE sections with an alignment > 4.

[ruiu]

In D59531#1445628, @grimar wrote:

In D59531#1445429, @ruiu wrote:

Hmm, if some tools are setting a large alignment (greater than 4) to a .note section by mistake, then we probably should ignore them and treat them as a 4 byte alignment rather than respecting a wrong value. That means always setting alignment of 4 to every .note input section.

Sounds a bit hacky IMO. I would expect from linker to make as fewer assumptions as possible.

I.e. if some tool "setting a large alignment (greater than 4) to a .note section by mistake",
I would expect we would at least report a warning before adjusting the alignment?
And ideally the tool needs to be fixed and we then will remove that temporary workaround from the linker after some time.

I don't agree. I feel like we are worrying too much about unrealistic scenario. The reality is that some tool accidentally sets 8 bytes alignment to a .note section while they should have been 4 bytes. Since it is a .note section, no one that reads the section care whether it was aligned to 8 bytes or 4 bytes. We could make up a scenario in which a .note alignment matters, but I'd think that's probably a pathetic use case (and probably an inappropriate use of the section.)

[grimar]

In D59531#1450938, @ruiu wrote:

In D59531#1445628, @grimar wrote:

In D59531#1445429, @ruiu wrote:

Hmm, if some tools are setting a large alignment (greater than 4) to a .note section by mistake, then we probably should ignore them and treat them as a 4 byte alignment rather than respecting a wrong value. That means always setting alignment of 4 to every .note input section.

Sounds a bit hacky IMO. I would expect from linker to make as fewer assumptions as possible.

I.e. if some tool "setting a large alignment (greater than 4) to a .note section by mistake",
I would expect we would at least report a warning before adjusting the alignment?
And ideally the tool needs to be fixed and we then will remove that temporary workaround from the linker after some time.

I don't agree. I feel like we are worrying too much about unrealistic scenario. The reality is that some tool accidentally sets 8 bytes alignment to a .note section while they should have been 4 bytes. Since it is a .note section, no one that reads the section care whether it was aligned to 8 bytes or 4 bytes. We could make up a scenario in which a .note alignment matters, but I'd think that's probably a pathetic use case (and probably an inappropriate use of the section.)

OK.

[jakehehrlich]

The larger alignment isn't being set by mistake there's just an odd note that's being added to linux binaries right now and its causing this sort of headache.

In D59531#1445689, @peter.smith wrote:

If I've understood the latest patch right then pcc's original test case will still fail if both notes sections in the example below are 4-byte aligned.

SECTIONS {
  . = SIZEOF_HEADERS;
  .note1 : { *(.note1) }
  . = 0x10000;
  .note2 : { *(.note2) }
}

If this is still the intention to support this case then it would be good to add a test case.

It would fall back to the original behavior for this case which is acceptable for this patch.

[jakehehrlich]

@ruiu and others. I'm still good to land this as is. Are you ok with me landing this?

[MaskRay]

In D59531#1480947, @jakehehrlich wrote:

@ruiu and others. I'm still good to land this as is. Are you ok with me landing this?

If the intention is just to fix .note.gnu.property, we don't have to differentiate OneProgramHeaderPerNoteSection and MultiNoteSegmentLayout. We can just merge consecutive SHT_NOTE sections if Last->Align == Current->Align && Last->Size % Last->Align == 0. Assuming the compilers emit 4-byte aligned notes followed by 8-byte aligned notes, we will have at most 2 PT_NOTE segments and will not incur the 56-byte (Phdr size) per note overhead every time they add a new note section.

BTW, binutils has introduced a new segment type PT_GNU_PROPERTY to address the alignment issue (https://sourceware.org/bugzilla/show_bug.cgi?id=23900). I think it may be too early for us to follow suit.

[MaskRay]

lld/test/ELF/multiple-notes.s

14 ↗

(On Diff #192536)

I'd like to see .align 8 instead of .align 16. I think the emitters only create 4-byte and 8-byte aligned notes and their sizes are padded so that size%align == 0.

[MaskRay]

See https://reviews.llvm.org/D61296

[ruiu]

I'm still thinking that overriding .note section alignment with 4 is the best way to fix the issue. Setting it to 8 is a tool's bug, and fundamentally the .note section format does not seem to be designed to accommodate something whose alignment requirement is greater than 4 exactly because of this issue.

[MaskRay]

In D59531#1492971, @ruiu wrote:

I'm still thinking that overriding .note section alignment with 4 is the best way to fix the issue. Setting it to 8 is a tool's bug, and fundamentally the .note section format does not seem to be designed to accommodate something whose alignment requirement is greater than 4 exactly because of this issue.

@ruiu Sorry for being hurry (D61296). Forcing p_align=4 doesn't work if some systems interpret notes according to the alignment, as a sequence of Elf64_Words or a sequence of Elf64_Xwords (suggested by some people in https://groups.google.com/forum/#!searchin/generic-abi/SHT_NOTE%7Csort:date/generic-abi/TRJYlEklEfM/Wrz-0kXOAgAJ)

When systems started to move towards 64 bits, HP-UX followed gABI and used 8-byte alignment (Elf64_Xword n_namesz, n_descsz, n_type;. This is probably not what they actually use but the struct definition here eases thinking). Many (including Linux, Solaris, NetBSD) diverged (Elf64_Word n_namesz, n_descsz, n_type;). We can't blame them much, the gABI description isn't so clear about the caveat.

On these systems, some notes are established and can't be changed (.note.ABI-tag .note.gnu.build-id). Some newly invented (including .note.gnu.property) notes start to use 8-byte alignment. When a 4-byte aligned note is followed by an 8-byte aligned note, the interpretation of the 8-byte aligned note may be difficult: some consumers may expect a padding while some may not.

[ruiu]

This thread is long and we might have discussed this, but have you considered sorting .note sections by alignment? *If* the size of a .note section with 8 bytes alignment is always a multiple of 8 (not sure if that's true), sorting .note sections might be able to fix the issue.

[MaskRay]

In D59531#1493064, @ruiu wrote:

This thread is long and we might have discussed this, but have you considered sorting .note sections by alignment? *If* the size of a .note section with 8 bytes alignment is always a multiple of 8 (not sure if that's true), sorting .note sections might be able to fix the issue.

The thread is long, and there is another long thread in the gnu-abi mailing list :) I tried summarizing their points in my previous comment and in my commit description.

Someone suggested interpreting notes as Elf64_Word n_namesz, n_descsz, n_type; or Elf64_Xword n_namesz, n_descsz, n_type; according to p_align. The former is for compatibility while the latter is for gABI conformance. (It is very bad that since 2015 nobody maintains gABI.) This interpretation makes it fundamentally impossible to mix 4-byte aligned and 8-byte aligned notes in one PT_NOTE segment. The section header is not read by many consumers.

lld/ELF/Writer.cpp

template <class ELFT> std::vector<PhdrEntry *> Writer<ELFT>::createPhdrs() {
 
   // PT_OPENBSD_WXNEEDED is a OpenBSD-specific header to mark the executable
   // is expected to perform W^X violations, such as calling mprotect(2) or
   // mmap(2) with PROT_WRITE | PROT_EXEC, which is prohibited by default on
   // OpenBSD.
   if (Config->ZWxneeded)
     AddHdr(PT_OPENBSD_WXNEEDED, PF_X);
 
-  // Create one PT_NOTE per a group of contiguous .note sections.
+  // Create one PT_NOTE per a group of contiguous .note sections with
+  // alignment such that notes can be parsed in order.
   PhdrEntry *Note = nullptr;
+  OutputSection *LastNote = nullptr;
   for (OutputSection *Sec : OutputSections) {
     if (Sec->Type == SHT_NOTE && (Sec->Flags & SHF_ALLOC)) {
+      bool NewNote = false;
+      if (LastNote) {
+        uint64_t Align = MinAlign(LastNote->Alignment, LastNote->Size);
+        Align = std::max(Align, uint64_t(4));
+        NewNote = NewNote || Align < Sec->Alignment;
+      }
       if (!Note || Sec->LMAExpr)
+        NewNote = true;
+      if (NewNote)
         Note = AddHdr(PT_NOTE, PF_R);
       Note->add(Sec);
+      LastNote = Sec;
     } else {
       Note = nullptr;
     }
   }
   return Ret;
 }
 
 template <class ELFT>
 void Writer<ELFT>::addPhdrForSection(std::vector<PhdrEntry *> &Phdrs,
                                      unsigned ShType, unsigned PType,
                                      unsigned PFlags) {
   auto I = llvm::find_if(
       OutputSections, [=](OutputSection *Cmd) { return Cmd->Type == ShType; });

lld/test/ELF/build-id.s

 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=DEFAULT %s
 
 .globl _start
 _start:
   nop
 
 .section .note.test, "a", @note
    .quad 42
+   .byte 42
+
+# 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
 
 # ALIGN:      Name: .note.gnu.build-id
 # ALIGN-NEXT: Type: SHT_NOTE
 # ALIGN-NEXT: Flags [
 # 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
 
 # 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: 4a1b8629 1147db29
 
 # MD5:      Contents of section .note.gnu.build-id:
 # MD5-NEXT: 04000000 10000000 03000000 474e5500  ............GNU.
-# MD5-NEXT: 6a51bbd7 9e8ee3f9 2e02d213 711cfec9
+# MD5-NEXT: 0a9aaf86 8158723b 36bf8535 a32e0625
 
 # SHA1:      Contents of section .note.gnu.build-id:
 # SHA1-NEXT: 04000000 14000000 03000000 474e5500  ............GNU.
-# SHA1-NEXT: 9a8618b1 d6fd0e5c eda73dd8 76de5596
+# SHA1-NEXT: f66aa8ea 3fe906c6 99fc5c52 6678d3a8
 
 # 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:

lld/test/ELF/large-align-notes.s

+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+
+# RUN: ld.lld %t -o %t2
+# RUN: llvm-readobj -l %t2 | FileCheck %s
+
+.globl _start
+_start:
+  nop
+
+# Has 4-byte aligned size and alignment
+.section .note.std1, "a", @note
+  .align 4
+  .quad 0
+
+# Has > 4-byte alignment but aligned size
+.section .note.large, "a", @note
+  .align 16
+  .quad 0
+
+# Has 4-byte aligned size and alignment. Should be coalesced.
+.section .note.std2, "a", @note
+  .align 4
+  .quad 0
+
+# We need a split for the next part of this test
+.section .note.split, "a", @note
+  .align 16
+  .quad 0
+
+# To test the case where a less algined section that comes first is still
+# merged with the section below because the alignment is still less than 4 we
+# create a section with alignment 1 and size 1
+.section .note.small, "a", @note
+  .align 1
+  .byte 1
+
+# Now because notes bump to 4 byte alignment, the next note section should be
+# merged
+.section .note.std3, "a", @note
+  .align 4
+  .quad 0
+
+#CHECK:       ProgramHeader {
+#CHECK:         Type: PT_NOTE (0x4)
+#CHECK-NEXT:    Offset:
+#CHECK-NEXT:    VirtualAddress:
+#CHECK-NEXT:    PhysicalAddress:
+#CHECK-NEXT:    FileSize: 8
+#CHECK-NEXT:    MemSize: 8
+#CHECK-NEXT:    Flags [ (0x4)
+#CHECK-NEXT:      PF_R (0x4)
+#CHECK-NEXT:    ]
+#CHECK-NEXT:    Alignment: 4
+#CHECK-NEXT:  }
+#CHECK-NEXT:  ProgramHeader {
+#CHECK-NEXT:    Type: PT_NOTE (0x4)
+#CHECK-NEXT:    Offset:
+#CHECK-NEXT:    VirtualAddress:
+#CHECK-NEXT:    PhysicalAddress:
+#CHECK-NEXT:    FileSize: 16
+#CHECK-NEXT:    MemSize: 16
+#CHECK-NEXT:    Flags [ (0x4)
+#CHECK-NEXT:      PF_R (0x4)
+#CHECK-NEXT:    ]
+#CHECK-NEXT:    Alignment: 16
+#CHECK-NEXT:  }
+#CHECK-NEXT:  ProgramHeader {
+#CHECK-NEXT:    Type: PT_NOTE (0x4)
+#CHECK-NEXT:    Offset:
+#CHECK-NEXT:    VirtualAddress:
+#CHECK-NEXT:    PhysicalAddress:
+#CHECK-NEXT:    FileSize: 20
+#CHECK-NEXT:    MemSize: 20
+#CHECK-NEXT:    Flags [ (0x4)
+#CHECK-NEXT:      PF_R (0x4)
+#CHECK-NEXT:    ]
+#CHECK-NEXT:    Alignment: 16
+#CHECK-NEXT:  }
+#CHECK-NEXT:]