Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline

[ELF] - Implemented basic location counter support.
ClosedPublic

Authored by grimar on Mar 27 2016, 7:16 AM.

Details

Summary

This patch implements location counter support.
It also separates assign addresses for sections to assignAddressesScript() if it scipt exists.

Main testcase is test/ELF/linkerscript-locationcounter.s, It contains some work with location counter. It is basic now.
Implemented location counter assignment and '+' operations.

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
ruiu added inline comments.Apr 1 2016, 11:06 AM
ELF/LinkerScript.h
71 ↗(On Diff #52364)

Why do you need this function? If the linker script directly assign VAs to sections, we don't need this.

grimar updated this revision to Diff 52399.Apr 1 2016, 11:30 AM
grimar marked an inline comment as done.
  • Addressed review comments.
ELF/LinkerScript.h
71 ↗(On Diff #52394)

If so - yes.

ELF/Writer.cpp
1417 ↗(On Diff #52394)

Misunderstanding :) I thought you want to have Script->getSecVA() method.
Without that all life is easier of course.
Removed whole method.

1421–1425 ↗(On Diff #52394)

Nope. Removed.

ruiu added inline comments.Apr 1 2016, 3:31 PM
ELF/LinkerScript.cpp
36 ↗(On Diff #52399)

It seems that we don't need this class because this class has only one member, LocCounter and you always reset LocCounter before calling evaluate. This class can just be a function that takes the current VA and an expression and returns a new VA.

72 ↗(On Diff #52399)

It is better to move this variable inside LinkerScript.

109 ↗(On Diff #52399)

Does this have to be a lambda?

125 ↗(On Diff #52399)

Why do you have to remove the element here?

267–270 ↗(On Diff #52399)

The concept of dummy sections seems a bit confusing. Could you improve it?

ELF/LinkerScript.h
52–54 ↗(On Diff #52399)

I wouldn't use the same variable for completely different purposes. I'd define two fields, Expr and SectionName, instead.

grimar added inline comments.Apr 2 2016, 2:17 AM
ELF/LinkerScript.cpp
109 ↗(On Diff #52399)

Please see answer in below comment.

125 ↗(On Diff #52399)

I need to visit all output sections to assign addresses for each.
Script can mention only some of them.
There were 2 choices I saw:

  1. Make this lambda and do 2 iterations. First iteration visits everything that was directly mentioned in script. During that it removes the sections if found from global list. After that we will have all unvisited sections in this global list. Then second iteration visits them all.

That gives 2 iterations, but complexity is O(n) in total.

  1. In this variant it is possible to insert all sections that were not mentioned in script to Locations list at the begining of method and avoid using lambda. That would be one loop. Problem here that is that if we have OutputSectionBase list and have Locations lists then how to find those sections for which LocationNode was not created to vizit ?

That would be something like (pseudocode):

for (OutputSectionBase<ELFT> *Sec : S) {
  if (S NOT IN Locations) {
    Locations.push_back(create location for S);
  }
}

That is O(N^2) part of code that can be inserted at the begining of this method, that can help to get rid of labmda and do all in one iteration.

ruiu added inline comments.Apr 2 2016, 7:55 AM
ELF/LinkerScript.cpp
125 ↗(On Diff #52399)

This is a bit too convoluted. It'd need a few trial-and-errors, but it should be able to be written in a straightforward way. I'd probably start making this lambda a separate function.

610 ↗(On Diff #52399)

Exist -> Exists

629 ↗(On Diff #52399)

Remove S.

ELF/LinkerScript.h
48 ↗(On Diff #52399)

I'd make this a enum class and rename members as shown below.

LocNodeType -> Command
LocSet -> Expr
LocOutSet -> Section

ELF/Writer.cpp
228 ↗(On Diff #52399)

Let's name this assignAddresses for consistency with the Writer.

grimar added a comment.Apr 2 2016, 8:06 AM

Ok, thank you for review, I`ll address this all later today/tomorrow I think (except dummies).

ELF/LinkerScript.cpp
267–270 ↗(On Diff #52399)

I guess you mean not only for this patch but whole dummies approach, right ?
We can probably just get rid of them, like we had before ?

ruiu added inline comments.Apr 2 2016, 8:11 AM
ELF/LinkerScript.cpp
267–270 ↗(On Diff #52399)

Yes, I'm talking about the approach itself. I'm not sure what you mean by "just get rid of them" (can we do that? I think we need some replacements for them,) but the point is that the code here for the dummy sections seem a bit too complex, so it needs to be improved.

grimar added inline comments.Apr 2 2016, 8:16 AM
ELF/LinkerScript.cpp
267–270 ↗(On Diff #52399)

Ok. When I say "get rid" I mean that some time ago they were not sections. So we definetely can do that and just the question "how to do this better now ?" left. I`ll try to suggest some patch to change that.

grimar added inline comments.
ELF/LinkerScript.cpp
267–270 ↗(On Diff #52399)

So, my suggestion patch about dummies sections is D18743.

I`ll update/rebase this as soon as D18743 be landed (If will). The last one can help to simplify the code of this I think.

grimar updated this revision to Diff 52893.Apr 7 2016, 3:46 AM
grimar marked 7 inline comments as done.
  • Addressed review comments.
ELF/LinkerScript.cpp
36 ↗(On Diff #52399)

Done.

72 ↗(On Diff #52399)

Since that class not exist, variable also not exist anymore.

125 ↗(On Diff #52399)

Done. Made lambda as separate function + refactored code to have only one iteration.

610 ↗(On Diff #52399)

Done.

629 ↗(On Diff #52399)

Done.

ELF/LinkerScript.h
48 ↗(On Diff #52399)

Done.

52–54 ↗(On Diff #52399)

Done.

ELF/Writer.cpp
228 ↗(On Diff #52399)

Done.

grimar updated this revision to Diff 53242.Apr 11 2016, 7:39 AM
  • Rebased
ruiu added inline comments.Apr 11 2016, 2:14 PM
ELF/LinkerScript.cpp
424 ↗(On Diff #53242)

I think you should remove addLocation function and directly add new elements to Locations vector since you intentionally merge two different control flow into one function and dispatch again using the first argument. That's just confusing.

ELF/LinkerScript.h
47 ↗(On Diff #53242)

Let's make this an enum class because it currently adds "Section" and "Expr" to lld::elf namespace.

48 ↗(On Diff #53242)

Add blank line before this struct definition.

74 ↗(On Diff #53242)

Arg -> Args

grimar updated this revision to Diff 53374.Apr 12 2016, 2:26 AM
  • Addressed review comments.
ELF/LinkerScript.cpp
424 ↗(On Diff #53242)

Removed.

ELF/LinkerScript.h
47 ↗(On Diff #53242)

Done.

48 ↗(On Diff #53242)

Done.

74 ↗(On Diff #53242)

There is no such method anymore.

ruiu added inline comments.Apr 12 2016, 12:59 PM
ELF/LinkerScript.cpp
51–65 ↗(On Diff #53374)

Define this method

uint64_t getInteger(StringRef S) {
  uint64_t V;
  if (S.getAsInteger(0, V)) {
    setError("malformed number: " + V);
    return 0;
 }
  retrurn V;
}

Then you can simplify this to

StringRef Tok = Tokens[I];
if (Tok == ".")
  Result += LocCounter;
else
  Result += getInteger(Tok);
94 ↗(On Diff #53374)

Are you aware of the fact that StringMap copies keys? Maybe DenseMap is more efficient because it doesn't copy StringRefs?

113 ↗(On Diff #53374)

Needs () around &.

131 ↗(On Diff #53374)

This function seems a bit too complicated. This function construct temporary data to feed to setSectionsAddresses. Do we really need to do that? Isn't there any way to make it simpler?

154 ↗(On Diff #53374)

Flip the condition and use early continue.

grimar updated this revision to Diff 53563.Apr 13 2016, 8:13 AM
grimar marked 4 inline comments as done.
  • Addressed review comments.
ELF/LinkerScript.cpp
51–65 ↗(On Diff #53374)

Done.
Btw, few iterations ago I had code like this.
http://reviews.llvm.org/D18499?id=52399#inline-156527
Looks when you requested to make a single function from whole class I understood this too straightforward (combined exactly into one function) :)

94 ↗(On Diff #53374)

I missed that fact. Thanks for pointing on that.
There is no such method and variable anymore.

113 ↗(On Diff #53374)

Done.

131 ↗(On Diff #53374)

Reimplemented in much more straighforward way.

154 ↗(On Diff #53374)

There is no such code anymore.

grimar added inline comments.Apr 13 2016, 10:11 AM
ELF/LinkerScript.cpp
95 ↗(On Diff #53563)

At the same time if we talk about perfomance then I think most narrow place is lookup and not creation of container.
So I can guess StringMap still was faster since it does not recompute hash during lookup.
I didn't check since code was cut off.

ruiu added inline comments.Apr 13 2016, 2:27 PM
ELF/LinkerScript.cpp
98–99 ↗(On Diff #53563)

Although it is technically correct that what we are doing here is different from the doc, I don't think it necessarily mean it needs to be marked as "FIXME". My impression is that if you control section layout using linker scripts, you need to give complete layout. So please remove "FIXME" label from this comment and just state the fact:

Orphan sections are sections present in the input files which are not explicitly placed into the output file by the linker script. We place orphan sections at end of file. Other linkers places them using some heuristics as described in https://sourceware.org/binutils/docs/ld/Orphan-Sections.html#Orphan-Sections.

ELF/LinkerScript.h
69 ↗(On Diff #53563)

fixUp -> fixup

grimar updated this revision to Diff 53682.Apr 14 2016, 3:08 AM
  • Addressed review comments.
ELF/LinkerScript.cpp
98–99 ↗(On Diff #53563)

My impression is that if you control section layout using linker scripts, you need to give complete layout.

Perfect, done ! I was thinking about the same often. For me it was always a bit wierd that linker do something on his own when script is given. That complicates the whole things at the same time privides no strict rules, but only heuristics, what can be confusing.
I was not sure that is acceptable to change that behavior though.

ELF/LinkerScript.h
69 ↗(On Diff #53563)

Done.

ruiu added a comment.Apr 14 2016, 12:26 PM

Please update the commit message. This is not a prototype even though its feature is limited. This is a patch that will be committed as part of the linker.

ELF/LinkerScript.cpp
40 ↗(On Diff #53682)

You probably have to do this

error("malformed number: " + Twine(V))
115 ↗(On Diff #53682)

Call fixupLocations here instead of exporting it and call it from the Writer.

129–130 ↗(On Diff #53682)

This shouldn't happen now, no?

485–492 ↗(On Diff #53682)

Remove.

ELF/LinkerScript.h
68–69 ↗(On Diff #53682)

Make it private.

grimar updated this revision to Diff 53875.Apr 15 2016, 6:35 AM
grimar marked 4 inline comments as done.
  • Addressed review comment.
ELF/LinkerScript.cpp
40 ↗(On Diff #53682)

I think what I want is:

error("malformed number: " + S);

Updated testcase.

115 ↗(On Diff #53682)

Done.

129–130 ↗(On Diff #53682)

This can happen. Imagine asm code:

.global _start
_start:
 nop

and script that contains section description, but this section is absent in code above:

SECTIONS {
 .stub : { *(.stub) }
}

Since there is no such section, OutputSections list will not contain it, but location node will still be created and needs to be skipped then.

485–492 ↗(On Diff #53682)

Done.

ELF/LinkerScript.h
68–69 ↗(On Diff #53682)

Done.

grimar retitled this revision from [ELF] - Implemented prototype of location counter support. to [ELF] - Implemented basic location counter support..Apr 15 2016, 6:38 AM

About D19107 and SectionOrder vector.
What about landing this and eliminating the SectionOrder at all ?

At fact when we have Locations structure, SectionOrder is just a subset. We can use
Locations instead to sort sections in compareSections.

The only problem then - that fixupLocations() should be called much earlier then.
I think previous iteration was better for such purposes.

grimar updated this revision to Diff 53886.Apr 15 2016, 8:00 AM
  • Fixed clang warning.
ruiu accepted this revision.Apr 15 2016, 10:42 AM
ruiu edited edge metadata.

LGTM

This revision is now accepted and ready to land.Apr 15 2016, 10:42 AM
In D18499#402693, @ruiu wrote:

LGTM

Thank you for all these reviews of that !

This revision was automatically updated to reflect the committed changes.