This is an archive of the discontinued LLVM Phabricator instance.

[ELF] Produce multiple PT_NOTE segments as needed
AbandonedPublic

Authored by jakehehrlich on Mar 18 2019, 7:18 PM.

Details

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).

Diff Detail

Repository
rL LLVM

Event Timeline

jakehehrlich created this revision.Mar 18 2019, 7:18 PM
pcc added a comment.Mar 18 2019, 7:56 PM

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

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

?

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 added a comment.Mar 19 2019, 7:19 AM
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 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 added a comment.Mar 19 2019, 1:23 PM
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.

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.

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 edited the summary of this revision. (Show Details)

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 added a comment.Mar 20 2019, 4:44 PM

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 added inline comments.Mar 20 2019, 4:45 PM
lld/ELF/Writer.cpp
2038–2039

This comment is no longer accurate.

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 added a subscriber: grimar.Mar 21 2019, 3:05 AM

Looks OK for me too.

lld/test/ELF/multiple-notes.s
20

a PT_NOTE I guess?

jhenderson added inline comments.Mar 21 2019, 3:15 AM
lld/test/ELF/multiple-notes.s
4

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

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.

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.

Added Roland's proposed fix

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 added a comment.Mar 27 2019, 5:44 PM

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 added a comment.EditedMar 28 2019, 2:14 AM

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.

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
2037–2038

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.

2039

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 added a comment.Apr 1 2019, 8:46 PM

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 added a comment.Apr 2 2019, 1:36 AM

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.

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.

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.

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

@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 added inline comments.Apr 26 2019, 6:36 PM
lld/test/ELF/multiple-notes.s
15

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 removed a subscriber: MaskRay.
jakehehrlich abandoned this revision.May 3 2019, 12:42 PM
ruiu added a comment.May 7 2019, 12:35 AM

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.

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 added a comment.May 7 2019, 1:48 AM

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.

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/test/ELF/multiple-notes.s