llvm dev - Jan 2016 - Need to refactor relocation handlers in ELF LLD

On Thu, Jan 21, 2016 at 6:10 AM, Rafael Espíndola <
rafael.espindola at gmail.com> wrote:
> On 21 January 2016 at 04:11, Rui Ueyama <ruiu at google.com> wrote:
> > We have fairly large and complex code to handle relocations in
> Writer.cpp,
> > Target.cpp, OutputSections.cpp and InputSections.cpp. They started
with
> > simple code, but because each patch added a small piece of code to the
> > existing one, it is becoming out of control now. For example, we have
> lots
> > of entangled boolean flags in the functions that interfere with each
> other
> > in an obscure fashion. Even I don't understand all these
interactions.
> >
> > We need to clean this up to get it back to be manageable. The code in
> > SymbolTable.cpp is for example pretty much readable and in my opinion
> > beautiful. I want the relocation handlers to be as readable as that
is.
> >
> > I think there are a few things we can to do to fix the problem.
> >
> > 1. I'd like everybody to not add any more complexity to the
relocation
> > handler until we clean this up because as we add more code, it gets
> harder
> > to refactor. Any patch to reduce complexity is welcome.
>
> I agree. A short moratorium while we experiment with refactoring
> sounds reasonable.
>
> > 2. The fact that we don't create SymbolBodies for local symbols is
one of
> > the major factors to contribute that complexity. I experimented on
> creating
> > them, and the performance penalty seemed to be within a few percent,
so
> > that's a good trade-off. I'll try that. We can offset that
degradation
> with
> > optimizations in other places.
>
> I would like to leave this as a last resort. Putting things that don't
> take part in symbol resolution into the symbol resolution is confusing
> IMHO.
>
I don't think so, as the symbol plays a major role not only in symbol
resolution but also in relocation application. It is easier to model that
all relocations point to symbols. That is true in ELF so that's a direct
modeling of the ELF structure. Let me try to experiment -- we can abandon
the idea if it becomes clear that that doesn't worth.

>
> > 3. We probably want to separate relocation relaxation from relocation
> > application. Currently it is a unified pass, but theoretically we can
> split
> > it up into two, so that we do relaxation and then apply remaining
> > relocations.
>
> I agree with this one. A similar comment applies for deciding if we
> need a dynamic relocation and actually creating it.

Good point. Looks like visiting relocations sequentially is pretty fast
because they are continuous in memory, so I expect that the cost of
iterating over them a few times is marginal.
> My bar for readability may be a little bit high, but I strongly believe
> that
> > that will eventually increase overall productivity. I really need help
> from
> > LLD developers to keep it readable and hackable. I'd greatly
appreciate
> any
> > patch to reduce complexity. Thanks!
>
> Thanks a lot for the work at making lld easier to understand.
>
> I was away from coding and catching up on code review, but I agree
> that this is important and will try to improve things a bit in here
> before going back to code review (and then LTO).
>
> What I will probably try first is reordering output so that we don't
> need to compute the size upfront. That should give us quite a bit of
> flexibility in refactoring anything else. I don't know if it will be
> too costly, but I will report on anything I find.
>
I don't know if computing the size upfront increased complexity. Was it?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160121/e9138e46/attachment-0001.html>

>> I would like to leave this as a last resort. Putting things that
don't
>> take part in symbol resolution into the symbol resolution is confusing
>> IMHO.
>
>
> I don't think so, as the symbol plays a major role not only in symbol
resolution but also in relocation application. It is easier to model that
all relocations point to symbols. That is true in ELF so that's a direct
modeling of the ELF structure. Let me try to experiment -- we can abandon
the idea if it becomes clear that that doesn't worth.

Sure. At this point we should try a few experiments and see what works.
.
>
>> > My bar for readability may be a little bit high, but I strongly
believe that
>> > that will eventually increase overall productivity. I really need
help
from
>> > LLD developers to keep it readable and hackable. I'd greatly
appreciate any
>> > patch to reduce complexity. Thanks!
>>
>> Thanks a lot for the work at making lld easier to understand.
>>
>> I was away from coding and catching up on code review, but I agree
>> that this is important and will try to improve things a bit in here
>> before going back to code review (and then LTO).
>>
>> What I will probably try first is reordering output so that we
don't
>> need to compute the size upfront. That should give us quite a bit of
>> flexibility in refactoring anything else. I don't know if it will
be
>> too costly, but I will report on anything I find.
>
>
> I don't know if computing the size upfront increased complexity. Was
it?
It is. That is what requires that in two points in the code we come up the
same answer as to whether a relocation is optimized for example.

If we didn't need to know that we could centralize the knowledge: write,
regular sections, relocate, write dynamic relocations.

Changing it is an experiment both in complexity and performance, but I
should hopefully have a proof of concept tomorrow.

Cheers,
Rafael
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160121/4797abf6/attachment.html>

On Thu, Jan 21, 2016 at 11:59 AM, Rafael Espíndola <
rafael.espindola at gmail.com> wrote:
> >> I would like to leave this as a last resort. Putting things that
don't
> >> take part in symbol resolution into the symbol resolution is
confusing
> >> IMHO.
> >
> >
> > I don't think so, as the symbol plays a major role not only in
symbol
> resolution but also in relocation application. It is easier to model that
> all relocations point to symbols. That is true in ELF so that's a
direct
> modeling of the ELF structure. Let me try to experiment -- we can abandon
> the idea if it becomes clear that that doesn't worth.
>
> Sure. At this point we should try a few experiments and see what works.
> .
>
> >
> >> > My bar for readability may be a little bit high, but I
strongly
> believe that
> >> > that will eventually increase overall productivity. I really
need
> help from
> >> > LLD developers to keep it readable and hackable. I'd
greatly
> appreciate any
> >> > patch to reduce complexity. Thanks!
> >>
> >> Thanks a lot for the work at making lld easier to understand.
> >>
> >> I was away from coding and catching up on code review, but I agree
> >> that this is important and will try to improve things a bit in
here
> >> before going back to code review (and then LTO).
> >>
> >> What I will probably try first is reordering output so that we
don't
> >> need to compute the size upfront. That should give us quite a bit
of
> >> flexibility in refactoring anything else. I don't know if it
will be
> >> too costly, but I will report on anything I find.
> >
> >
> > I don't know if computing the size upfront increased complexity.
Was it?
>
> It is. That is what requires that in two points in the code we come up the
> same answer as to whether a relocation is optimized for example.
>
> If we didn't need to know that we could centralize the knowledge:
write,
> regular sections, relocate, write dynamic relocations.
>
> Changing it is an experiment both in complexity and performance, but I
> should hopefully have a proof of concept tomorrow.
>
I guess that you are trying to layout sections that have fixed size first
and then other sections that vary in size (such as GOT, string tables,
etc.) after them.

But users can enforce some ordering using linker script. Is it going to be
compatible with that?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160121/2f95056f/attachment.html>