Need to refactor relocation handlers in ELF LLD

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.

  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.

  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.

  4. Last but not least, any code that is not obvious needs explanation in comment, so that first-time readers who have basic knowledge on ELF can read and understand the code. Even if code is very simple, comment may be needed, because readers may want to know not only what is to be done but also why we want to do that for what.

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!

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.

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.

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.

Cheers,
Rafael

​​I will look at relocation relaxations closer tomorrow, may be will be able to suggest something to reduce complexity a bit.​

> 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?

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

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?

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?

Not exactly fixed size first. But there are some restrictions, like
the relocation section has to be after section that need dynamic
relocations. There are no restrictions on the order of user sections.

Cheers,
Rafael