Page MenuHomePhabricator

[LLVM][llvm-objcopy] Added basic plumbing to get things started
ClosedPublic

Authored by jakehehrlich on Jun 6 2017, 3:46 PM.

Details

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
  1. Sometimes sections that don't belong in segments would wind up in a PT_LOAD segment that had Offset == 0. This is fixed by only adding allocated sections to segments (see Object::readSectionHeaders)

I disagree with this approach - yes non-allocatable sections should not end up in PT_LOAD (although using linker scripts, I wouldn't be surprised if it is possible), but it is perfectly legitimate to have segments that are not loadable with non-SHF_ALLOC sections (see the ongoing discussion in D34204 for explanation). I'm not quite sure what the case here is that you've encountered, but it sounds to me like the issue is elsewhere.

Also, I noticed that you don't ignore SHT_NULL sections, but you probably should. Large proposal 74 ELFs with many sections have metadata stored in that section. I'd suggest two things:

  1. Don't add support for Prop74 just yet - you can check somewhere if it is one and then bail out, to be safe.
  2. Skip the SHT_NULL section when reading section headers, and recreate it later on.
tools/llvm-objcopy/Object.cpp
108

This should probably be SHT_STRTAB || SHT_NULL.

I decided to just skip index zero rather than all SHT_NULL sections. It's equivalent for normal files but also handles strange files that want to have SHT_NULL sections in the middle for some reason.

Having the dummy section be treated as a real section was causing the issue I had to fix with the SHF_ALLOC check so fixing this killed two birds with one stone.

I decided to just skip index zero rather than all SHT_NULL sections. It's equivalent for normal files but also handles strange files that want to have SHT_NULL sections in the middle for some reason.

Having the dummy section be treated as a real section was causing the issue I had to fix with the SHF_ALLOC check so fixing this killed two birds with one stone.

Great! One minor nit, and I think we're nearly there, from my point of view. Also, at things stand, very large proposal 74 ELFs with metadata in the SHT_NULL section will be corrupted silently, I believe, so it might be nice to error if there are too many sections when trying to write.

tools/llvm-objcopy/Object.cpp
129–130

Sec->Index = Index++?

Fixed the separate index assignment and increment.

jhenderson added inline comments.Jul 3 2017, 1:38 AM
tools/llvm-objcopy/Object.cpp
162

address order -> offset order

186

Could you explain why we are using a mix of offsets and addresses here, as it is surprising to me.

197

properlly -> properly

198–199

Why only the sh_name field? 4-byte alignment could cause other struct members to be misaligned (e.g. the sh_addr and sh_offset fields), because they are 8-bytes in size.

Fixed some small issues like the comments recommend by James.

jakehehrlich marked 5 inline comments as done.Jul 5 2017, 4:29 PM
jakehehrlich added inline comments.
tools/llvm-objcopy/Object.cpp
186

The first an main point is that the Offsets change in this loop and what we want to respect is the difference between the section offsets in the original file. FirstInSeg->Offset no longer respects that information. This is changeable however by adding fields that keep track of the original file offset. This might make sense to use elsewhere as well like in the sorting algorithm where we're trying to respect the original offset as much as possible. This would free up Offset to be messed with (in what way isn't clear) before sorting occurs. So this is changeable but only by adding another field. Perhaps that is not a bad idea however.

This said when I was thinking about this I never actually even thought to use Offset. I was thinking about respecting the memory image not the file image. I think as a guiding principal "respect the memory image" is a a better guiding principal but only slightly. The memory image and file image should agree for all valid files however so I'm not really opposed to changing it. I have a slight opposition but it's based on some ideas I have for changing the file layout algorithm and I don't want to justify code here based on code that hasn't been written yet. The general idea is that it is possible to enforce "respect the memory image" via const correctness/encapsulation but it is not possible to do the same for the file image because Offset will need to be changed.

My personal opinion is that adding a new Offset like field that isn't quite Offset and using that field to compute the new offset here isn't really any clearer that what I have here. What do you think?

198–199

The next field (sh_type) is also a 4-byte word and thus anything after those two will be 8-byte aligned. So this is the minimal alignment I can choose which ensures that all the fields of the section header are aligned. I updated the comment to reflect this fact.

By the way, although it makes it easier for me to see the changes, your current diff only shows the changes versus the previous diff, so has lost, for example, the tests.

As noted in one of my comments, I'm not certain that this will work in the nested segment case. Is there a test for this?

tools/llvm-objcopy/Object.cpp
186

I think I follow what you're saying and broadly agree with it. We have to respect the memory image, at least for linked objects, because if we change the relative positions of two sections within a segment, then the address mapping will no longer be correct. For relocatable objects, that's not an issue, because they don't have a memory mapping yet (and segments can be ignored in this case).

However, the file and memory image are not always consistent, even for valid programs. Specifically, SHT_NOBITS sections have no file image typically, but do have a memory image. Usually, this is not an issue, because the .bss section is placed at the end of the data segment. However, when using TLS (which is sometimes a nested segment in the data segment) this is not the always the case due to .tbss, because other non-TLS data usually appears after it. From my observations, different platforms exhibit different behaviour here, but at least some of them have no file image assigned for the .tbss section, but do have a memory image associated with it. As such, the layout algorithm needs to be able to handle this case.

That all being said, looking at the code without actually trying it out, I'm not convinced that this will handle the nested-segment case anyway, in which case what you've got here is fine. However, I would suggest updating the comment to explain why we need to respect interstitial memory gaps.

198–199

Relative to the start of the section header, the fields will be aligned correctly. However, relative to the start of the file, they won't be: for example, in 64-bit ELF, with 8 byte address fields, the sh_name field was aligned to offset 4, the sh_type field will be at offset 8, and the 8-byte-sized sh_flags field will be at offset 12, which is misaligned.

  1. I was wrong about the alignment of section headers as James pointed out. I fixed that.
  2. Added comments recommended by James.
  3. This is the full diff that I forgot to add last time
jakehehrlich marked 7 inline comments as done.Jul 6 2017, 1:03 PM
jakehehrlich added inline comments.
tools/llvm-objcopy/Object.cpp
198–199

Yep. You're right. I did my math wrong. Not sure what I was thinking there. Thanks for catching that! It should be fixed now.

Could you construct a test case that confirms the behaviour of nested segments, please? Something with a memory image like:

| Segment 1                                                        |
| Segment 2                               |
| Progbits Section | gap | NOBITS section | gap | Progbits section |
test/tools/llvm-objcopy/hello-world.s
2 ↗(On Diff #105513)

I don't think this will work for many people, as LLD is not part of LLVM's main source code body, so people will be unable to run this test. That being said, I'm not sure how to work around this. Can yaml2obj help us here? (I'm not particularly familiar with that tool yet).

tools/llvm-objcopy/Object.cpp
186

I'd suggest changing the second and third sentence to something like:

"We *must* maintain the memory image so that addresses are preserved. As, with the exception of SHT_NOBITS sections at the end of segments, the memory image is a copy of the file image, we preserve the file image as well."

It explains why the file and memory image need to match, which may not be obvious to those who are unfamiliar with ELF.

jakehehrlich marked 4 inline comments as done.Jul 10 2017, 11:09 AM

Could you construct a test case that confirms the behaviour of nested segments, please? Something with a memory image like:

| Segment 1                                                        |
| Segment 2                               |
| Progbits Section | gap | NOBITS section | gap | Progbits section |

I can confirm this just won't work right. As is the first Progbits section will wind up in two Segments and everything will get all messed up. For this diff I'm fine with that not being supported. I'm also not sure what the intended behavior is in this case.

test/tools/llvm-objcopy/hello-world.s
2 ↗(On Diff #105513)

Oh man, that didn't even occur to me. As far as I am aware there is no way to produce program headers using yaml2obj. It never produces any program headers by default either. I think you're right and this should be fixed. I have no clue how to fix it other than adding support for program headers to yaml2obj. That's not something I've looked into however.

Perhaps there is a way to require lld for this test? That way it's just unsupported for most people?

Fixed the comment as recomended

jakehehrlich marked an inline comment as done.Jul 10 2017, 11:12 AM

Could you construct a test case that confirms the behaviour of nested segments, please? Something with a memory image like:

| Segment 1                                                        |
| Segment 2                               |
| Progbits Section | gap | NOBITS section | gap | Progbits section |

I can confirm this just won't work right. As is the first Progbits section will wind up in two Segments and everything will get all messed up. For this diff I'm fine with that not being supported. I'm also not sure what the intended behavior is in this case.

I'm ok with that as well, but I'd like to understand what your plan is going forward to fix this, in case it has a significant impact on the design.

Having a progbits section in multiple segments is absolutely fine, and I'd expect the layout to be maintained as in the diagram. The alignment of all containing segments needs to be respected when placing the first section, and then they all start at the same place (or in the case where the nested segment is not at the start, at the same relative offset). There are some weird oddities when coming to NOBITS sections, because of their file/memory footprint mismatch. The simple, but probably undesirable, option is to allocate a file footprint for any NOBITS sections that are not at the end of the top-most parent segment. I think though that actually, as is the case in the diagram here, that there is special handling for nested NOBITS sections like this in loaders (specifically, I'm thinking of the .tbss case again - the example could easily be a data segment with a nested TLS segment, with the .tdata, .tbss, and .data sections). By my understanding, as long as .tbss is at the end of the nested TLS segment, it should not have a file footprint, even though it makes it look like there'll be a mismatch in the data segment.

test/tools/llvm-objcopy/hello-world.s
2 ↗(On Diff #105513)

I'm afraid I don't know of a way. There might be, but if there is, somebody else will have to advise.

It seems to me that having program header support in yaml2obj is very desirable. I'd offer to add it, but I do not have any time to do so.

I'm ok with that as well, but I'd like to understand what your plan is going forward to fix this, in case it has a significant impact on the design.

Having a progbits section in multiple segments is absolutely fine, and I'd expect the layout to be maintained as in the diagram. The alignment of all containing segments needs to be respected when placing the first section, and then they all start at the same place (or in the case where the nested segment is not at the start, at the same relative offset). There are some weird oddities when coming to NOBITS sections, because of their file/memory footprint mismatch. The simple, but probably undesirable, option is to allocate a file footprint for any NOBITS sections that are not at the end of the top-most parent segment. I think though that actually, as is the case in the diagram here, that there is special handling for nested NOBITS sections like this in loaders (specifically, I'm thinking of the .tbss case again - the example could easily be a data segment with a nested TLS segment, with the .tdata, .tbss, and .data sections). By my understanding, as long as .tbss is at the end of the nested TLS segment, it should not have a file footprint, even though it makes it look like there'll be a mismatch in the data segment.

Well if this is in fact the intended behavior then I think that means I have to switch from "respect the memory image" to "respect the file image". If the relative offsets are used instead of relative addresses it should solve this problem with only a tiny change. If I stick to "respect the memory image" then I'd have to add all sorts of complicated book keeping to ensure that this case was handled correctly. Even if TLS isn't handled this way there might be some case like this where it is and we should respect the choice that the file made. I think this case (or even the possibility of such a case existing) convinces me that it should be "respect the file image" and not "respect the memory image".

So to handle this I propose the following changes:

  1. Make the parent segment the lowest offset segment. I think I'd prefer "lowest offset segment" rather than "top segment" in order to account for strange things like overlapping segments in case those are also a thing. I'm slowly coming to realize that it's best to curtail my assumptions as much as possible.
  2. Change "Offset = FirstInSeg->Offset + Section->Addr - FirstInSeg->Addr;" to "Offset = FirstInSeg->Offset + Section->OriginalOffset - FirstInSeg->OriginalOffset;" because of the TLS case you found. This way we respect the choice the input file made on this mater regardless of weather it allocates space in the file for the NOBITS section or not.
  3. Add a parent segment field to segments so that nested segments (and even overlapping segments) can have offsets based on their parent segment and not the sections they contain.

Does this sound good? If so I'll go ahead and change this diff to use 1) and 2) now and I'll add 3) in another diff. Even with just 1) and 2) I think this should still work in the specific case you requested a test on but I'll wait to add that test when I add 3) I think.

test/tools/llvm-objcopy/hello-world.s
2 ↗(On Diff #105513)

I'm adding support for program headers to yaml2obj now. Hopefully I can land that change soon.

I've spent a fair amount of time today investigating GNU objcopy's behaviour for nested segments. The quick version is that it can get into a slightly broken state if you start messing about with sections in nested segments (although it does the right thing for the normal use cases).

I used an artificial linker script to create an arbitrary nested segment with four non-empty sections in: 3 progbits sections followed by a nobits section. In the parent segment, I also added additional progbits sections and concluded with a nobits section. If objcopy is used to strip one of the progbits sections in the nested segment, the file image is left unchanged, as expected, but perhaps bizarrely, the memory image of the segment gets messed up - the addresses of the sections are unchanged, but the memory image of the segment has unexpectedly shrunk. I suspect this is a bug. The behaviour of the TLS sections gets even weirder, and there appears to be a lot of special case handling which causes things to go wrong when additional segments get stripped, so I highly recommend never adding custom sections to the TLS segment!

Anyway, that all aside, from my investigations and my understanding, what you are proposing seems good. Preserving the relative file offsets will be sufficient to cover all cases that I'm aware of, regardless of how the linker has chosen to allocate file and memory space in the segment for sections.

The overlapping segment case is weird, and I'm not sure how to construct an ELF in that state. What you are proposing sounds reasonable for this as well. The only thing I would say is consider the case where Segment1 overlaps the start of Segment2, which in turn overlaps the start of Segment3. As long as Segment3 gets moved relative to Segment1 (possibly indirectly by moving relative to Segment2), I think we're fine.

  1. Offsets of sections that cover a segment are no longer based on relative addresses but on relative offsets from the original file. This accounts for the normal case and the strange TLS case that James pointed out and it does so regardless of weather the target system makes this choice or not for TLS.
  2. If a section covers multiple segments then the parent segment is now canonicalized to be the lowest offset segment
jhenderson added inline comments.Jul 13 2017, 2:10 AM
tools/llvm-objcopy/Object.cpp
96–102

From a code readability point, it might be worth either breaking this into a small helper function, or to explain the algorithm in comments somewhere.

I'm not asking you to add them at this point, but this is the sort of thing that would be great to have unit-tests around!

194

I've just thought about yet another problem with this:

In some cases, the ELF header and/or Program Header table can appear in a segment before the first section. Consequently, we need to preserve the relative offset to the start of the section, rather than the first segment. At the moment, any space before the first section within the segment is ignored and lost.

This applies to Segment::finalize() too.

220

typo: remaining

262–272

Nothing is using Shdr here. Is this missing a write, or can it be removed?

tools/llvm-objcopy/Object.h
58

Two sections with identical addresses will be considered identical by the set, which means that only one will be present. I'm pretty sure overlapping sections are bad, but an empty section could easily share the same start address without any worry. I think you need to compare the pointers themselves to prove they are not identical, i.e. the check becomes:

if (Lhs->Addr == Rhs->Addr)
  return Lhs < Rhs;
return Lhs->Addr < Rhs->Addr;

Optionally, you could test other members as well, e.g. Offset or Size, but ultimately, you're going to need to test that they are not the same section somewhere.

Please also add a test case for this (e.g. two identical empty sections at the same address and offset, or one empty and one non-empty section at the same address and offset).

77

if (!Sections.empty()) maybe?

137–142

The size of some of these fields is dependent on the Elf Type (64 versus 32). I wonder if these should be based on ELFT? On the other hand, I'm quite happy that we just use the largest size for now.

At the moment, since the template is only instantiated for Elf64LE, this is fine, but it won't work once 32-bit support is added, unless the point where they are assigned to the Elf Header struct is modified to cast the values accordingly.

  1. Changed firstSection to use !empty() instead of implicitly converting size() to a bool
  2. Segments should now keep track of empty sections. I don't think this would have caused an issue but I agree that it is a problem none the less. It shouldn't ever affect layout but it could affect other analysis.
  3. Added a helper "is covered by" method to clean things up as recommended by James
  4. Fixed a spelling mistake pointed out by James
jakehehrlich marked 5 inline comments as done.Jul 13 2017, 5:53 PM
jakehehrlich added inline comments.
tools/llvm-objcopy/Object.cpp
194

Yea PT_PHDR is a problem I have run into in extensions of this diff. I think it needs some special handling. I think I can support it when I officially add support for copying data of interstitial gaps and nested segments. It will still require special care however. Would you be ok with me not attempting to handle this right now? At the very least this requires handling nested segments because the PT_PHDR segment must be nested in a PT_LOAD segment.

The needed information is preserved now because the original offset of the segment is stored until the segment offset needs to be computed and the original offset of the section is now stored and kept. So that gap can be recovered when performing layout of the segment. This seems to be enough to confirm that there isn't a fundamental design issue that prevents the PT_PHDR case from being handled.

262–272

This is actually correct I believe. This does point out a lack of clarity in what is going on here however.

As is every section knows where their header belongs so I just pass "Out" to the section and it does the rest. This highlighted code writes the dummy section at the start of the section header table. So there's no missing write or anything. I'll add a comment explaining what's going on here.

tools/llvm-objcopy/Object.h
137–142

This was a recommendation that I got from Rui actually. To quote Rui when speaking about LLD.

  • Integral types such as Elf{32,64}_{XWord,Word,Addr,Offset} are not useful and better to avoid. We are using uint{8,16,32,64}_t instead. It seems it improves readability. (I honestly don't memorize > the real types of these ELFT types.)
  • ELFT::uint, whose size is 32/64 depending on ELF32/64, isn't useful. Always uint64_t to represent a value that can be 32 or 64. The waste of doing this is negligible, but it could drastically simplify > types because if your function uses only ELFT::uint, you can de-template that function by using uint64_t.

I've found this to be true as well. It definitely lets you get rid of a lot of templates. If we just used the templates when you had access to them (Like in Object here) and used the largest type when we didn't (like in Segment or SectionBase) we would get this strange inconsistency in our code. I'd like to avoid that.

Thanks for adding empty-section.s. Once you have program header support in yaml2obj, I think it would be good to have the same test for empty sections in program headers, for similar reasons (actually, the way the code was written, I think that test would be the more important one).

tools/llvm-objcopy/Object.cpp
80–81

It's not clear on the surface what is meant by "Covers" (I assume it means within or similar). Also, I think you've got it backwards in the name - it returns true, if the section is in the segment, not the other way around.

Also, I'm not sure what the behaviour of empty sections should be here. My instinct is to say that empty sections are "covered" by a segment, if they appear at the start, or in the middle of a segment, but not if it is only at the end. I could imagine a case with two segments with the first having the same end offset as the start of the next one. If there is an empty section at the meeting point, I don't think it makes sense for it to be in both. From a run-time point of view, I don't think it matters, but it could cause weird looking anomalies in static dumping tools, and also leads to the case of, "if the first segment moves to a lower offset, does the section move with it or stay with the other segment?"

194

I'm not sure it's specific to PT_PHDR - it's possible to put these headers in any arbitrary segment, if you want (though I'm not sure why you would in most cases), e.g. directly in the first PT_LOAD segment, with the appropriate linker script. Also, I don't think it's specific to the headers either - the file image is going to get messed up if there was empty space of any kind not covered by a section before the first section. Rather than preserve the relative offsets of sections to the first section, this code should probably preserve the offset relative to the original segment start.

Example:

| Segment                   |
| gap | Section1 | Section2 |
A     B

The offset of Section1 will be placed at A, if I've followed the code correctly, not at B, where it should be, thus messing up the file and therefore the memory image. Section2 will still be placed immediately after Section1 correctly.

As a side point, this will also have an impact on the alignment of the first section, but assuming the input program is valid, I don't think that this will be an issue.

262–272

Ah, I missed the fact that this was a reference rather than a copy. What you are doing here is fine then. A comment might be helpful though, as you say.

tools/llvm-objcopy/Object.h
137–142

Ok, that's fine with me, as long as it was a conscious decision. I could see a case in the future when adding support for things like adding or modifying sections when it may be important to safety check that we haven't overflowed, but that's not relevant at the moment.

jakehehrlich marked 3 inline comments as done.Jul 14 2017, 3:55 PM
jakehehrlich added inline comments.
tools/llvm-objcopy/Object.cpp
80–81

I agree, "covers" is not the right word here. I'll say "within" or "inside of" I suppose. I thought I was using "cover" in the colloquial sense it is used when referring to these things but apparently I did not use it correctly. I thought it was an odd way to refer to things. I'll just refrain from using that term.

Oh weather an empty section should belong to a segment I agree and came to the same conclusion by the same reasoning. I plan on never modifying segment size or contents however so I don't think this will cause an issue.

194

The difference between this case and the PHDR case is that it's easy to allocate space for t his gap during layout but it is not easy to retroactively figure out that this segment should be covering the program headers which is space that is not even up for allocation from the perspective of the current algorithm. I'm going to upload a new diff that handles this case but does not handle the PHDR case.

  1. Fixed "sectionCoversSegment" confusion
  2. Segments with gaps at the start are now preserved
  3. Clarified how the SHT_NULL section was being added

One more issue that I've put inline, along with a couple of comment typos, and then there's only the tests to sort out. Good work!

It would be good to get somebody else's eyes on this though, given the scale of the new code.

tools/llvm-objcopy/Object.cpp
92

"belongs" to the second section and -> "belongs" to the second segment and

206

asign -> assign

225

I think this only should happen when the section is not in a segment. Otherwise, the section will move independently of the segment, and thus break our file image preservation. In most cases this is a no-op anyway, because the alignment should already be met, but in the case of slightly dodgy input (misaligned section within a segment), we should probably avoid making things worse by breaking the memory image.

If you do this, the comment at the start of the for loop should be updated.

fixed comment typos

Ok, I'm now completely happy with the code as is (barring one more nit in a comment). Just the testing left.

I don't know how you're getting on with segments and yaml2obj, but there is precedent for checking in pre-built binaries in the Lit tests, if it's not possible to create the inputs from raw assembly or similar. That might be a way forward if yaml2obj support is going to take some time.

tools/llvm-objcopy/Object.cpp
227

Nit: I'd use "if this section is in a segment" instead of belonged in, because something might belong in something else, but for whatever reason wasn't put in there.

I clarified the comment that James mentioned

I'm hoping to get the yaml2obj program headers change pushed though this week and I'm hoping BigCheese will give this a look. A lot has changed since he last looked at it. I'll also see if Petr can't give this another look. BigCheese should be back from the ISO meeting so hopefully he can give it a look this week. So maybe, just maybe, I'll land this this week or early next week.

Bigcheese accepted this revision.Jul 18 2017, 3:29 PM

Looks good after you fix the use of lld in hello-world.s

This revision is now accepted and ready to land.Jul 18 2017, 3:29 PM
  1. Fixed test case issue by removing hello-world.s and adding program-headers.test
  2. Removed some unneeded headers
This revision was automatically updated to reflect the committed changes.
  1. Fixed MSan issue. I was not initlizing all fields of StringNames and the parent segment was sometimes uninitialized. A method "makeSection" was added to handle creation of sections so that it is all done in one place rather than spread out.
  2. Hopefully fixed a fatal warning on a mac build be removing a variable deceleration

Somehow I messed up and uploaded the old hello-world.s test. This fixes that

Is there any way yet in yaml2obj for it to add program headers which cover more than just the stated sections (in file and memory terms)? It might be nice to have a test that simulates a segment with nobits sections in, and/or arbitrary gaps before and after sections.

Otherwise the tests look good to me as they currently stand.

Added MC as a dependency. This resolves the error when building on i686-mingw32-RA-on-linux

Some builds fail when using "make_unique" because "std::make_unique" is sometimes defined. I fixed it to use llvm::make_uinque everywhere

There was an issue on windows that caused a "permission denied" error. I *think* this is being caused by tool_output_file also opening a handle to the file and windows not allowing writing to such a file. I removed the tool_output_file code

Added llvm-objcopy to test/CMakeLists.txt

  1. Switched the ordering on sections in segments to use OriginalOffset instead of Address. This should be the same in general but also handles non-allocated sections being added to non PT_LOAD segments and is consistent with the rest of the code in the system.
  2. Added llvm-objcopy to lit.cfg. This caused an odd incompatibility on windows but not linux
  3. Added addresses to program-header.test. Without this the tests are invalid and before change 1) this would cause undefined behavior in the ordering of sections in segments because the address was 0x0 for everything. For some reason this error only occurred on windows. It would appear that the allocator on linux increases memory addresses monotonically and this caused the bug to be disguised. So now tests are valid