Page MenuHomePhabricator

Fix handling of zero-size segments in llvm-objcopy
ClosedPublic

Authored by vit9696 on Feb 2 2018, 3:25 PM.

Details

Summary

Some ELF files produced by lld may have zero-size segment placeholders as shown below.
Since GNU_STACK Offset is 0, the current code makes it the lowest used offset, and relocates all the segments over the ELF header. The resulting binary is total garbage.

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  LOAD           0x001000 0xc0000000 0x10000000 0x48000 0x48000 R E 0x1000
  LOAD           0x04c000 0xc0048000 0x10048000 0x155e0 0x67000 RW  0x4000
  GNU_STACK      0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x0

Section Headers:
  [Nr] Name              Type            Address  Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .text             PROGBITS        c0000000 001000 01e7d4 00  AX  0   0  4
  [ 2] .vector_table     PROGBITS        c001e7d4 01f7d4 000038 00   A  0   0  4
  [ 3] .rodata           PROGBITS        c001e80c 01f80c 0297f4 00 AMS  0   0  4
  [ 4] .data             PROGBITS        c0048000 04c000 0155e0 00  WA  0   0 16384
  [ 5] .bss              NOBITS          c0060000 0615e0 04f000 00  WA  0   0 16384
  [ 6] .ARM.attributes   ARM_ATTRIBUTES  00000000 0615e0 00002f 00      0   0  1
  [ 7] .debug_line       PROGBITS        00000000 06160f 015219 00      0   0  1
  [ 8] .debug_info       PROGBITS        00000000 076828 01e940 00      0   0  1
  [ 9] .debug_abbrev     PROGBITS        00000000 095168 00435f 00      0   0  1
  [10] .debug_aranges    PROGBITS        00000000 0994c7 0000e8 00      0   0  1
  [11] .debug_str        PROGBITS        00000000 0995af 008095 01  MS  0   0  1
  [12] .debug_ranges     PROGBITS        00000000 0a1644 0000a0 00      0   0  1
  [13] .debug_macinfo    PROGBITS        00000000 0a16e4 00003a 00      0   0  1
  [14] .debug_pubnames   PROGBITS        00000000 0a171e 004fc6 00      0   0  1
  [15] .debug_pubtypes   PROGBITS        00000000 0a66e4 007099 00      0   0  1
  [16] .comment          PROGBITS        00000000 0ad77d 000045 01  MS  0   0  1
  [17] .debug_frame      PROGBITS        00000000 0ad7c4 004740 00      0   0  4
  [18] .debug_loc        PROGBITS        00000000 0b1f04 000522 00      0   0  1
  [19] .symtab           SYMTAB          00000000 0b2428 003a50 10     21 469  4
  [20] .shstrtab         STRTAB          00000000 0b5e78 0000f0 00      0   0  1
  [21] .strtab           STRTAB          00000000 0b5f68 004252 00      0   0  1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), l (large)
  I (info), L (link order), G (group), T (TLS), E (exclude), x (unknown)
  O (extra OS processing required) o (OS specific), p (processor specific)

Diff Detail

Repository
rL LLVM

Event Timeline

vit9696 created this revision.Feb 2 2018, 3:25 PM
ruiu added a subscriber: ruiu.Feb 5 2018, 4:28 PM

Can you write a test for this change?

It is not specific to lld by the way. GNU linkers also create these marker segments with virtual address zero.

What tells us that a segment is a marker segment? I think FileSize == 0 is probably a good choice but I want to make sure we don't later have to come back and fix this.

As I see it there are a few issues with what I originally wrote

  1. My code assumes that the only way a program header will have offset zero is if there is a PT_PHDR header. We should probably check for a PT_PHDR header and follow the ParentSegment pointers up until its a nullptr to get the proper starting offset
  2. My code assigns offsets to program headers that shouldn't have offsets assigned to them (like PT_GNU_STACK). We should either make a general rule like "if FileSize == 0 then don't assign an offset" or we should keep a list of program header types that should be excluded.

Also, please add a test to make sure I don't mess this up in the future.

jakehehrlich added inline comments.Feb 6 2018, 8:10 PM
tools/llvm-objcopy/Object.cpp
915 ↗(On Diff #132695)

Can you add a comment explaining the following

  1. Explain why we need to remove such segments.
  2. By not adding such a segment to OrderedSegments we are not going to tweak the Offset of the segment from the OriginalOffset.
  3. Segments with FileSize == 0 will never be the ParentSegment of a section or other Segment so not tweaking their offset will never cause the offset of another section or segment to be invalid.

I added James Henderson as I seem to recall we had this issue some time ago and apparently I added the problem back again somewhere along the way. I seem to recall James had an opinion on what counted as a dummy segment. Knowing past me I probably conservatively said a dummy segment is a segment with MemSize zero. I think the less conservative answer of if FileSize is zero is better now though. Alternatively we could try and make a comprehensive list of every dummy PT_* type

@jhenderson, @ruiu what do you think? what should indicate that the offset of a segment should be left alone?

jhenderson requested changes to this revision.Feb 7 2018, 1:48 AM

I added James Henderson as I seem to recall we had this issue some time ago and apparently I added the problem back again somewhere along the way. I seem to recall James had an opinion on what counted as a dummy segment. Knowing past me I probably conservatively said a dummy segment is a segment with MemSize zero. I think the less conservative answer of if FileSize is zero is better now though. Alternatively we could try and make a comprehensive list of every dummy PT_* type

@jhenderson, @ruiu what do you think? what should indicate that the offset of a segment should be left alone?

I don't remember the details of our original discussion, but we cannot simply rely on FileSize being zero. Imagine a data segment with only .bss. It would need a file offset and address, and a MemSize, but no file size. At the very least, we need to pay attention to both. In the current state, such a segment will not be moved, which would be incorrect.

Also, we cannot rely on just the MemSize either, since although it is not common, I know of at least one target that has segments with no memory size, but which do have a file size - such segments contain informational contents, beyond just being a marker.

What tells us that a segment is a marker segment? I think FileSize == 0 is probably a good choice but I want to make sure we don't later have to come back and fix this.

I don't think there is any well-defined method for this, beyond knowing about specific segment types (possible by looking at the documentation for all known program headers). However, segments that are completely empty (both for file and memory contents) can probably all be harmlessly put at offset 0, or really anywhere, I guess.

  1. My code assumes that the only way a program header will have offset zero is if there is a PT_PHDR header. We should probably check for a PT_PHDR header and follow the ParentSegment pointers up until its a nullptr to get the proper starting offset.

I think it's actually legal to embed the elf header in a loadable segment, not necessarily nested inside a PT_PHDR, so I'd be wary about any assumption in this regards. We need to firstly find out which segment the program header table is in, using the elf header to determine the offset, and the program headers themselves to determine what covers it, and then use this information to perform the layout correctly.

This revision now requires changes to proceed.Feb 7 2018, 1:48 AM
vit9696 updated this revision to Diff 133171.EditedFeb 7 2018, 1:57 AM

Thanks for the comments!

I did not mean to offend lld or any other linker, the point was to state that the ELF was not something hand-crafted but actually a real-world example generated by a dedicated tool.

The reason I chose FileSize is entirely practical. A "non-marker" segment with FileSize of zero should be unable to affect any other segments, in my opinion. Even if such an ELF would be considered partially valid. From what I remember, there also exists GNU_RELRO, which overlaps a segment, but its VirtAddr won't be 0, and it is unrelated to the case.

Regarding the rest I included the comments and a test case.

Regarding the logic of the check, I should admit that:

  • this will not result in any segment removal;
  • the offset assigned to GNU_STACK will remain 0;
  • memory addresses are unaffected.

So both examples suggested by @jhenderson will be fine.

jhenderson added inline comments.Feb 7 2018, 2:11 AM
tools/llvm-objcopy/Object.cpp
916–923 ↗(On Diff #133171)

signalize about feature support -> signal support of a feature
overwrite ELF header -> overwrite the ELF header

The last sentence will also need updating once the check is changed (see below comment). I would assume that non-zero memsize of marker segments is not valid, since they won't contribute to the program image.

924 ↗(On Diff #133171)

This still doesn't work for a PT_LOAD data segment containing .bss only. With the code as-is, such a segment will not be added to OrderedSegments, and so will never have its offset adjusted, meaning that the offset will be incorrect. Such segments should have the conceptual offset of where they lie in the file. This affects things like dumping tools that try to map sections to segments, based on file layout.

Please add to your test such a segment (i.e. one with zero FileSize, non-zero MemSize).

vit9696 updated this revision to Diff 133181.Feb 7 2018, 2:38 AM

@jhenderson, sorry for my ignorance, but I miss the point of your .bss example just a second time. Could you elaborate a little more?

As I see it, if a file has a segment with a single .bss section with FileSize set to 0, this segment will not occupy any area in the file itself. For this reason setting its Offset to anything but zero makes no sense, because there could be no valid offset to the data in the file which is not existent.

I updated a test with a typo fix and included your comment rewording suggestions.

Also, I don't think yaml2obj supports segments with 0 FileSize and non-zero MemSize. Perhaps I simply failed to find a way to do it, in this case, could anyone give me a hint?

I couldn't find any reference in the standard for the program header offset, but for section offsets of NOBITS sections, there's this:

One section type, SHT_NOBITS described below, occupies no space in the file, and its sh_offset member locates the conceptual placement in the file.

I don't see why segment offsets should be any different. Also, by not adjusting the segment offsets of segments containing only NOBITS sections, the offset field of the section header for these sections will not be updated either, leaving the sh_offset field invalid.

For the record, linkers assign file offsets to such segments, after the previous segment, the same as if it had actual contents. When copying, GNU objcopy doesn't set the offset to zero, or similar (it leaves it unchanged, but then I haven't actually been able to create a case where the segment should be shifted yet).

Also, I don't think yaml2obj supports segments with 0 FileSize and non-zero MemSize. Perhaps I simply failed to find a way to do it, in this case, could anyone give me a hint?

Take a look at the yaml2obj test "program-header-nobits.yaml". That uses a segment with a larger memsize than filesize, and could be adjusted to not have any filesize at all, by removing the .data section.

@jhenderson, thanks, NOBITS makes a lot more sense to me than your previous example. Yet I am unaware of any software or even any tool that would rely on such on offset, and to my eyes the linkers are simply doing the wrong thing by not setting the offset of 0 for whatever reason. In my opinion being able to copy more ELF files, which will be most likely valid and loaded on a target system, is more important, than trying to support some shady offset to a non-existent memory nobody knows how to calculate.

I was able to produce the test case based on program-header-nobits.yaml, but I am not sure whether I should actually include it. Because as I stated above, whatever the offset is, it is undefined.

@jhenderson, thanks, NOBITS makes a lot more sense to me than your previous example. Yet I am unaware of any software or even any tool that would rely on such on offset, and to my eyes the linkers are simply doing the wrong thing by not setting the offset of 0 for whatever reason. In my opinion being able to copy more ELF files, which will be most likely valid and loaded on a target system, is more important, than trying to support some shady offset to a non-existent memory nobody knows how to calculate.

I can't claim to know what all the different consumers of ELF might do, but I think there's a non-zero chance of this change as-is breaking a system/program relying on the output produced by the linker. All I'm asking for is the check to be extended to test both MemSize and FileSize against 0. This should detect all marker segments safely, without potentially adversely affecting segments with non-zero MemSize. Also, not updating the offset will result in inconsistent behaviour beteween llvm-objcopy and linkers.

I was able to produce the test case based on program-header-nobits.yaml, but I am not sure whether I should actually include it. Because as I stated above, whatever the offset is, it is undefined.

I think calling it "undefined" is a bit of a stretch. It must follow the usual alignment requirements of p_vaddr % p_align == p_offset % p_align (or % page_size, depending on segment type). Certainly, leaving the p_offset unchanged will maintain this, assuming it was correct in the input, but, for example, setting it to zero (which "undefined" implies is valid) may not.

ruiu added a comment.Feb 7 2018, 11:27 AM

Ignoring sections with virtual memory size 0 and file size 0 is perhaps safe, but I wonder if we need to rely on the heuristics. There are only a few segment types that are used for "markers". Namely, you can ignore just PT_GNU_STACK and PT_OPENBSD_WXNEEDED. It seems to me that it's easier to understand than checking the segment size.

Ignoring sections with virtual memory size 0 and file size 0 is perhaps safe, but I wonder if we need to rely on the heuristics. There are only a few segment types that are used for "markers". Namely, you can ignore just PT_GNU_STACK and PT_OPENBSD_WXNEEDED. It seems to me that it's easier to understand than checking the segment size.

This seems like the right choice to me given that information. I didn't realize the list of program header types was so small. This is clearly the right way to do it.

ruiu added a comment.Feb 7 2018, 12:36 PM

This seems like the right choice to me given that information. I didn't realize the list of program header types was so small. This is clearly the right way to do it.

Yup. This is the list of all known segment types, and that's not many: https://github.com/llvm-project/llvm-project-20170507/blob/master/llvm/include/llvm/BinaryFormat/ELF.h#L1061

This seems like the right choice to me given that information. I didn't realize the list of program header types was so small. This is clearly the right way to do it.

I agree with this. It's also easy enough to extend the list if and when new program header types are added in the future.

I am personally not sure if it is the correct solution, because I do not understand why a segment with 0 filesize and a 0 offset should corrupt an ELF while copying regardless of its type.
I would personally prefer special-casing two segments to writing a check against both MemSize and FileSize, but it does not feel nice to me.
More importantly, if you have a PT_LOAD "marker" segment with all zero values:

  • will gnu binutils objcopy also corrupt such an ELF?
  • will a Linux/BSD-based system load such an ELF?

If in both cases the answer is no, then we should probably just special-case indeed, but I still cannot say that silently overwriting the header is any good. Perhaps we should print an error and abort?

More importantly, if you have a PT_LOAD "marker" segment with all zero values:

  • will gnu binutils objcopy also corrupt such an ELF?
  • will a Linux/BSD-based system load such an ELF? If in both cases the answer is no, then we should probably just special-case indeed, but I still cannot say that silently overwriting the header is any good. Perhaps we should print an error and abort?

I wouldn't define any PT_LOAD segment as a "marker" segment. Each segment type has a defined purpose, as defined by its type, so marker segments should only be those with types defined as marker types (i.e. PT_GNU_STACK and PT_OPENBSD_WXNEEDED).

That being said, I think we may be talking at cross-purposes here. Clearly overwriting the header is wrong, but a PT_LOAD segment with all zero values won't overwrite the header, since by definition it has zero size, and segments like this can and do occur, if they are empty. Furthermore, it is legal for the ELF header and program header table to be nested inside a segment, as long as that segment has an appropriate file offset. However, as we've seen here, the problem is that the layout code doesn't take account of the elf and program headers when laying out the remaining segments. Perhaps worrying about which segments should be treated as marker segments or not is the wrong approach, and really we should also treat the elf header and program header table as special in the LayoutSegments code. This would suggest a more correct approach to me: treat the ELF header and program header table as pseudo-segments for layout purposes, with an OriginalOffset of 0 and sizeof(ElfHeader) respectively. If they end up nested inside another segment, that's fine, as the segment by definition must be already in the right place. If they end up with segments nested inside them, that is also fine for the same reasoning. Zero-sized segments at offset 0 will still be placed at offset 0, as desired, but the ELF header segment will "follow" (at offset 0) immediately after it, since it will be the first non-empty segment in the ordered list (or will be nested inside another segment that is similarly at offset 0).

How does this sound as an approach? It feels more robust and avoids any special casing, since everything should just naturally work with the existing layout scheme (the only thing we'd have to do is write these pseudo-segments differently).

treat the ELF header and program header table as pseudo-segments for layout purposes, with an OriginalOffset of 0 and sizeof(ElfHeader) respectively. If they end up nested inside another segment, that's fine, as the segment by definition must be already in the right place. If they end up with segments nested inside them, that is also fine for the same reasoning. Zero-sized segments at offset 0 will still be placed at offset 0, as desired, but the ELF header segment will "follow" (at offset 0) immediately after it, since it will be the first non-empty segment in the ordered list (or will be nested inside another segment that is similarly at offset 0).

How does this sound as an approach? It feels more robust and avoids any special casing, since everything should just naturally work with the existing layout scheme (the only thing we'd have to do is write these pseudo-segments differently).

Ah this is the right way to handle PT_PHDR! I love this solution. 1) The initial offset is always zero 2) create two new program headers (giving them proper ParentSegments) 3) add them to ordered segments 4) Use the information from those headers to set values in the ELF header. This also properlly handles another issue I hadn't even thought about. If a program expects the program headers to be loaded and the program headers don't immediately follow the ELF header the current

It will be a little while before I can get to this though. Should we patch this for now and add a TODO?

I am personally not sure if it is the correct solution, because I do not understand why a segment with 0 filesize and a 0 offset should corrupt an ELF while copying regardless of its type.
I would personally prefer special-casing two segments to writing a check against both MemSize and FileSize, but it does not feel nice to me.
More importantly, if you have a PT_LOAD "marker" segment with all zero values:

  • will gnu binutils objcopy also corrupt such an ELF?
  • will a Linux/BSD-based system load such an ELF? If in both cases the answer is no, then we should probably just special-case indeed, but I still cannot say that silently overwriting the header is any good. Perhaps we should print an error and abort?

I think James' solution is the right way to handle this issue. As I stated I thought there were two issues before 1) I handle PT_PHDR incorrectly which causes this issue and 2) I assign invalid values to marker segments. James's solution resolves this issue 2) by avoiding special casing "marker" segments and solves issue 1) by having layout treat them the same way. So *really* the issue is that I didn't handle PT_PHDR segments the right way and this just happens to be how it blew up. Would you feel comfortable implementing James' solution? If not I'll eventually get around to it. Otherwise I'm happy temporarily using the "isMarker" special casing for PT_GNU_STACK and PT_OPENBSD_WXNEEDED along with a "TODO" assigned to me to implement James's solution.

I think I could have missed the point of the description a little, but I know of at least a total of 3 cases regarding ELF header:

  • ELF header is present in PT_LOAD segment
  • ELF header is mentioned in PT_PHDR segment
  • ELF header is not mentioned or present anywhere, but the segment data starts at a random offset the linker decided to use.

The file I have is the third case, and I think there is no way to find the real size of ELF header (and properly skip it) without iterating over the segments and finding the lowest Offset segment which FileSize is not zero. Correct me if I am wrong, but I do not see how the suggested approach gets around it.

I am not too opposed to writing a slightly larger patch, but I'd rather not do it in a wrong way, and due to the lack of proper ELF format format definitions it is very easy to.

If you are fine with the iteration & a FileSize check I should be able to update the patch with these changes in the reasonable future.

I think I could have missed the point of the description a little, but I know of at least a total of 3 cases regarding ELF header:

  • ELF header is present in PT_LOAD segment
  • ELF header is mentioned in PT_PHDR segment
  • ELF header is not mentioned or present anywhere, but the segment data starts at a random offset the linker decided to use.

    The file I have is the third case, and I think there is no way to find the real size of ELF header (and properly skip it) without iterating over the segments and finding the lowest Offset segment which FileSize is not zero. Correct me if I am wrong, but I do not see how the suggested approach gets around it.

The ELF Header has a defined size, based on whether 32-bit or 64-bit ELF is used, so a pseudo-segment (i.e. not one corresponding to the real one) could be created to cover it. The Program Header table's size and offset can be determined from the ELF Header's fields, so another pseudo-segment could be created to cover it. No special case handling would be needed after that, apart from to throw away these two segments at the end. This approach would work, regardless of whether the ELF Header and Program Headers are nested inside another segment.

I am not too opposed to writing a slightly larger patch, but I'd rather not do it in a wrong way, and due to the lack of proper ELF format format definitions it is very easy to.

Do you have a specific concern here that we can help with?

If you are fine with the iteration & a FileSize check I should be able to update the patch with these changes in the reasonable future.

If we want a small patch first, I'd prefer to replace the check with a segment type check rather than a FileSize check, due to previously stated reasons.

It is not that simple, because the size of the header part should be aligned to the page size (from what I remember at least). And we cannot know the alignment rules / page sizes of the target system. We could try checking the subsequent segments, but it is not so nice. I think that unless we replicate the area used by the header and the subsequent padding, the resulting ELF may become unloadable.

It is not that simple, because the size of the header part should be aligned to the page size (from what I remember at least)

I do not believe to be the case for the ELF header and program header table. What I therefore think you mean is that the first segment must be aligned based on the page size. From the ELF gABI:

loadable process segments must have congruent values for p_vaddr and p_offset, modulo the page size

What this means is that the first segment will often be at the first page-size boundary, although it is not required to be. I do not believe we take account of the page size in llvm-objcopy, thinking about this, but it doesn't matter, as long as the p_align field of loadable segments is at least the size of the page size. We should add a function that maps machine types to page sizes and use that to align loadable segments in general, although using p_align is likely good enough for most cases. In your case, is the p_align smaller than the page size? If it isn't, then the pseudo-segment approach will work without any issues, otherwise, we'll need to figure out the page size somehow.

And we cannot know the alignment rules / page sizes of the target system.

Can't we use the machine type? Or are there systems with different page sizes but the same machine type? If there are different, then the only way we can safely align things is by the page size being explicitly specified on the command-line. We cannot determine the page size just by inspecting the program headers.

We could try checking the subsequent segments, but it is not so nice.

I think you may also be making an incorrect assumption: there is no guarantee that all the loadable segments are first in the file. It is valid to have a loadable segment after a non-loadable segment, which means that we cannot use the position of the first non-empty segment as a basis to determine the page size.

That line from the gABI says the following

p_align
As ``Program Loading'' describes in this chapter of the processor supplement, loadable process segments must have congruent values for p_vaddr and p_offset, modulo the page size. This member gives the value to which the segments are aligned in memory and in the file. Values 0 and 1 mean no alignment is required. Otherwise, p_align should be a positive, integral power of 2, and p_vaddr should equal p_offset, modulo p_align.

e.g. loadable p_align gives the proper alignment and should be the system page size for the file to be properly loadable. We don't need to magically guess/know the system page size because the linker already did that for us and put the value in p_align. "loadable process segments must have congruent values for p_vaddr and p_offset, modulo the page size." is a requirement of loading not on the ELF. p_align is how the ELF encodges that information. The requirement for *all* program headers is that p_offset % p_align == p_vaddr % p_align and there is no other alignment constraint.

Well, ok, I think it might actually work this way. I will try to find some time in the next few days to update the patch.

That line from the gABI says the following

p_align
As ``Program Loading'' describes in this chapter of the processor supplement, loadable process segments must have congruent values for p_vaddr and p_offset, modulo the page size. This member gives the value to which the segments are aligned in memory and in the file. Values 0 and 1 mean no alignment is required. Otherwise, p_align should be a positive, integral power of 2, and p_vaddr should equal p_offset, modulo p_align.

e.g. loadable p_align gives the proper alignment and should be the system page size for the file to be properly loadable. We don't need to magically guess/know the system page size because the linker already did that for us and put the value in p_align. "loadable process segments must have congruent values for p_vaddr and p_offset, modulo the page size." is a requirement of loading not on the ELF. p_align is how the ELF encodges that information. The requirement for *all* program headers is that p_offset % p_align == p_vaddr % p_align and there is no other alignment constraint.

So apparently, I completely messed up interpreting a local example :/ Never mind, your understanding makes more sense than mine did!

vit9696 updated this revision to Diff 134055.Feb 13 2018, 9:23 AM

Well, I found some time to prototype what we discussed. As I got to the code I think I discovered more hidden issues that were not taken into account, and mentioned them as the comments in the code.

I used the following spec to base my thoughts on: http://www.skyfree.org/linux/references/ELF_Format.pdf

  1. The spec does not seem to define loadable segment alignment to be equal to the page size but only recommends doing that:
To obtain this efficiency in practice, executable and shared object files must have segment images whose file offsets and virtual addresses are congruent, modulo the page size.

I personally saw files with different loadable segment alignment values, in particular some segments had 4K and some other segments had 16K. I have never seen files where loadable segments had p_align less than page size, so for now I made an assumption that the lowest p_align value in PT_LOAD segments that is not 0 or 1, is no less than the page size.

  1. Next it appears that the spec does not guarantee us anything about program header table offset and size. So far I have never seen an ELF which program header table does not follow the ELF header, but the spec explicitly mentions that this is not a requirement:
Although the figure shows the program header table immediately after the ELF header, and the section header table following the sections, actual files may differ. Moreover, sections and segments have no specified order. Only the ELF header has a fixed position in the file.

This puts us to an uneasy situation, where we definitely know that the file starts with an ELF header, which is likely padded to the page size at least (if we assume that all the ELF files follow the optimisation suggestions from the spec), but other than that we can hardly make any assumptions.

Other than what I have already done I could imagine checking if the program header table overlaps with the first page.
If it does, we should ensure that the dummy segment includes the whole program header table.
If it does not, we should allocate another dummy segment for the program header table. Although I am even less sure of its size size and alignment in this case.

By the way, does llvm-objcopy support big endian ELFs on little endian host?

To clarify what I understood James to be proposing there should be two additional segments and they should not be added to Segments but instead OrderedSegments.

tools/llvm-objcopy/Object.cpp
461–462 ↗(On Diff #134055)

This is not needed. PageAlign is needed at all. IsHeaderInMemory shouldn't actully be computed, we should just add special segments to OrderedSegments that cover the headers and then if there already happened to be segments covering the program headers then so be it and if not that's fine also.

477–490 ↗(On Diff #134055)

None of this is needed.

505 ↗(On Diff #134055)

Don't add a header to segments here. Instead you should have two Segments as new members of Object, one for the ELF header and one for the program header table. The ELF header one should have pretty much all fields zero but importantly it *must* have the Offset as zero, the OriginalOffset as zero, the VAddr as zero, and the FileSize must be Elf_Ehdr. MemSize should be equal to FileSize for consistency. The index doesn't really matter here but I think doing what you're doing now (namely, Index = Index++) is best because it's sort of like we just happened to add two new members to the program header table.

515 ↗(On Diff #134055)

The FileSize should always be sizeof(Elf_Ehdr). It should never be PageAlign. I think you may be misunderstanding the spec. Here's the spec: http://www.sco.com/developers/gabi/2012-12-31/contents.html

520 ↗(On Diff #134055)

You'll also need to construct a program header table. Setting this up correctly is much trickier than the ELF header. You'll want to use ElfFile.getHeader() here. The Offset and OriginalOffset should be Ehdr->e_phoff, the FileSize and MemSize should be Ehdr->e_phentsize * Ehdr->e_phnum. The Type, for giggles, should be PT_PHDR. The VAddr actually matters here because it has to meet the important p_offset % p_align = p_vaddr % p_align. We also don't know what alignment it should meet this condition for. Luckily if we set p_vaddr to be the same as p_offset it will always hold *and* it won't effect layout if we do that either. I'd also like the index of this to be unique the way you did it for ElfHeader.

524 ↗(On Diff #134055)

Any artificially constructed segments (of which there will be two) will need to have their parent segments set. I think you should factor this inner loop out into a function so that you can later call it for the two constructed segments.

782 ↗(On Diff #134055)

This should go back to the old way after you get rid of the dummy segments stuff.

796–800 ↗(On Diff #134055)

This should go back to the old way after you get rid of the dummy segments stuff.

951–954 ↗(On Diff #134055)

You're going to need to modify this by adding two additional segments. If these two additional segments are members of Object you can just add their addresses at the end of the loop (which will also keep their Index order consistent).

tools/llvm-objcopy/Object.h
242 ↗(On Diff #134055)

We shouldn't need DummySegments as a new type of segment.

245 ↗(On Diff #134055)

We don't need this.

588 ↗(On Diff #134055)

We don't need or want this.

vit9696 updated this revision to Diff 134108.Feb 13 2018, 1:55 PM

Thanks for a quick reply. I think your comments were less helpful, because we had different assumptions, and you ended up explaining fairly trivial things leaving the ones I asked about unanswered. Apparently, assuming you got it right, I indeed misunderstood what James suggested. However, that's less important and easy to change.

More importantly,

The FileSize should always be sizeof(Elf_Ehdr). It should never be PageAlign. I think you may be misunderstanding the spec. Here's the spec: http://www.sco.com/developers/gabi/2012-12-31/contents.html

Here is what we had different assumptions about. And it is not the spec, this one is not perfect but pretty clear to me, but why would your code be happy with a random segment that is not contiguous to the other segments and possibly overlaps with the existing segments (e.g. when the program header table or elf header is mentioned in a loadable segment). I assumed that it won't work this way, and thus wrote the code to account for padding and stuff.

I rewrote the stuff in a way you suggested, and it worked fine for my ELF. However, I am currently on macOS and I do not have many real world examples (or time to review llvm-objcopy code) to say that this will work just fine in all the edge cases. Tests do pass at least.

Regarding PT_PHDR. I set the types of both added segments to PT_PHDR, because PT_LOAD segments must not overlap each other and other types fit even less. Neither 2, nor 3 PT_PHDR segments are allowed by the spec, but for now it should be fine.

I've answered these questions very out of order, I'm not really sure what order to answer them in however so I just answered them as I got to them. Also sorry about not properly explaining the reasoning behind all of this. Feel free to ask anymore questions. I've tried to provide an explanation for any confusion that might linger.

Regarding PT_PHDR. I set the types of both added segments to PT_PHDR, because PT_LOAD segments must not overlap each other and other types fit even less. Neither 2, nor 3 PT_PHDR segments are allowed by the spec, but for now it should be fine.

Yeah I couldn't really figure out what they should be. I think your choice is fine. I thought for a moment to ask you to make them PT_NULL but it dosn't really matter because they don't get written out.

This puts us to an uneasy situation, where we definitely know that the file starts with an ELF header, which is likely padded to the page size at least (if we assume that all the ELF files follow the optimization suggestions from the spec), but other than that we can hardly make any assumptions.

Prior to this change we incorrectly assumed that the program headers would occur directly after the ELF header. In practice this was a fair assumption but it leads to incorrect behavior if the program headers and elf header are covered by a program header. It's wrong and absolutely should be fixed. By having the ELF header and program headers added as extra segments that are also laid out we'll take care of that.

but why would your code be happy with a random segment that is not contiguous to the other segments and possibly overlaps with the existing segments.

Lots of segment types are always are overlapped. The mechanism by which this is handled is the ParentSegment member. The idea is that if segment A overlaps segment B then you can use segment A's previously assigned Offset to assign B's offset. If you carefully order the segments you can ensure that any segment with a parent segment has already had an Offset assigned to it. In fact there's an important behavoir that this change adds that wasn't handled before that this behavior needs to support. Say you have a PT_LOAD segment that starts at offset zero and a PT_PHDR segment that starts at 0x80. Normally the PT_PHDR segment would start at 0x40 but lets say for whatever reason the linker put it at 0x80. That would mean that code would assume that the program headers were at a location that they were in fact not in the way the current llvm-objcopy works. Your change should fix that however because the (now added extra program headers section) will be overlapped by the PT_LOAD segment, that PT_LOAD segment will be the ParentSegment of ProgramHdrSegment and then ProgramHdrSegment will be laid out correctly now.

Regarding finding these things out. It's a combination of reading, rereading, and seeing many crazy examples that technically meet the spec. I have the benefit of having a number of people I can talk to that have a deep knowledge of the spec. Sometimes you just have to ask unfortunately. On this particular point the spec never says segments can't overlap, it does say that sections can't overlap however.

I assumed that it won't work this way, and thus wrote the code to account for padding and stuff.

Totally fair. It turns out that not only is this handled but handling it any other way is likely error prone.

By the way, does llvm-objcopy support big endian ELFs on little endian host?

Yep, its 100% cross platform and it's behavior doesn't change from system to system. This is actually one of the primary use cases (the other is the fact llvm-objcopy isn't GPL). Chromium uses llvm-objcopy in a few cases instead of objcopy exclusively for this reason (well to support aarch64 from an x86 machine). In a change that's coming up I'll actually be allowing changes between big and little endian (not that that will ever be useful).

The spec does not seem to define loadable segment alignment to be equal to the page size but only recommends doing that

This is correct. Actually most loaders have this as a requirement because of the way hardware actully works. In theory there are valid PT_LOAD segments for x86 with less than 4k page size despite the fact that such hardware never existed. There are some technically valid ELF files that are not actually loadable. In llvm-objcopy we have to make the assumption that the linker already made all the right choices for us.

I personally saw files with different loadable segment alignment values, in particular some segments had 4K and some other segments had 16K. I have never seen files where loadable segments had p_align less than page size, so for now I made an assumption that the lowest p_align value in PT_LOAD segments that is not 0 or 1, is no less than the page size.

This is totally valid. Sometimes the system page size is larger than the hardware page size. Also keep in mind different systems might have different page sizes theoretically and sometimes they might be less than 4k even. You shouldn't need to infer the page size at all however.

tools/llvm-objcopy/Object.cpp
38 ↗(On Diff #134108)

I made an assumption here about where the program headers would actually go that was wrong. Instead of sizeof(Elf_Ehdr) this needs to be derived from ProgramHdrSegment to get the correct offset.

509 ↗(On Diff #134108)

The ParentSegments of ElfHdrSegment and ProgramHdrSegment still need to be set so that their layout happens properly.

763 ↗(On Diff #134108)

Whoops! I thought I added this comment but apparently not. This should get it's value from ProgramHdrSegment. The reason is to support the case where the program headers are overlapped by a PT_LOAD segment and the program headers aren't directly after the elf header. This doesn't really happen in practice which is why I've gotten this far without fixing it but now that you've solved that problem we should handle it correctly.

944 ↗(On Diff #134108)

Now that we always know we have a segment with Offset zero we should just set Offset to zero and remove the if-else statement below (which was a hack on my part).

vit9696 updated this revision to Diff 134172.Feb 14 2018, 1:43 AM

Thank you for such an involved explanation! It is pretty clear now I think. I applied all the mentioned changes and updated the diff.
In case there are no other issues may I ask you to commit this?

This is nearly there from my point of view. There are a few odd points in the inline comments which I'd like addressing before giving this the thumbs up, but they're only minor details. The solution is what I was imagining, and it's nice to see that everything just works (fingers-crossed!) with it.

test/tools/llvm-objcopy/marker-segment.test
53 ↗(On Diff #134172)

This segment should probably have a non-zero VAddr.

tools/llvm-objcopy/Object.cpp
459 ↗(On Diff #134172)

setParentSegments -> setParentSegment - a Segment can only have one Parent (it might of course have "grandparents" etc, but it's not directly relevant here).

503 ↗(On Diff #134172)

A quick comment explaining why we use PT_PHDR as the type would be wise.

516 ↗(On Diff #134172)

We should add comments for why we chose VAddr 0/e_phoff in these two locations.

519 ↗(On Diff #134172)

This should have Align = sizeof(Elf_Addr), as the spec requires all ELF fields to be "naturally" aligned (i.e. size 8 fields on an 8-byte boundary, 4 on a 4-byte etc). By setting Align to the size of an address, this will happen automatically.

945–948 ↗(On Diff #134172)

This comment needs updating/removing.

tools/llvm-objcopy/Object.h
563 ↗(On Diff #134172)

We should have a comment here explaining why we have these two special segments.

vit9696 updated this revision to Diff 134177.Feb 14 2018, 2:29 AM

Comments? But nobody reeeeads them anyway xD. Updated, kind of forgot about them.

jhenderson accepted this revision.Feb 14 2018, 3:00 AM

LGTM, with a couple of nits in the comments.

tools/llvm-objcopy/Object.cpp
945–948 ↗(On Diff #134172)

I might rephrase/extend this slightly. Something like:

"Offset is used as the start offset of the first segment to be laid out. Since the ELF Header (ElfHdrSegment) must be at the start of the file, we start at offfset 0."

tools/llvm-objcopy/Object.h
563 ↗(On Diff #134172)

case that ELF header -> case that the ELF header

This revision is now accepted and ready to land.Feb 14 2018, 3:00 AM
vit9696 updated this revision to Diff 134192.EditedFeb 14 2018, 3:33 AM

Done, could you merge it please?

Done, could you merge it please?

I'd like Jake to confirm that he's happy with it before this goes in, and I guess that he might as well commit it at that point, so I imagine it won't happen until tonight (my time).

jakehehrlich accepted this revision.Feb 14 2018, 2:51 PM

I'll land this today.

This revision was automatically updated to reflect the committed changes.

Thanks for working on this!

Thank you too!