This is an archive of the discontinued LLVM Phabricator instance.

[ELF] Make LinkerScript::assignAddresses iterative
ClosedPublic

Authored by MaskRay on Aug 15 2019, 2:22 AM.

Details

Summary

PR42990. For SECTIONS { b = a; . = 0xff00 + (a >> 8); a = .; },
we currently set st_value(a)=0xff00 while st_value(b)=0xffff.

The following call tree demonstrates the problem:

link<ELF64LE>(Args);
  Script->declareSymbols(); // insert a and b as absolute Defined
  Writer<ELFT>().run();
    Script->processSectionCommands();
      addSymbol(cmd);       // a and b are re-inserted. LinkerScript::getSymbolValue
                            // is lazily called by subsequent evaluation
    finalizeSections();
      forEachRelSec(scanRelocations<ELFT>);
        processRelocAux     // another problem PR42506, not affected by this patch
      finalizeAddressDependentContent(); // loop executed once
        script->assignAddresses(); // a = 0, b = 0xff00
    script->assignAddresses(); // a = 0xff00, _end = 0xffff

We need another assignAddresses() to finalize the value of a.

This patch

  1. modifies assignAddress() to track the original section/value of each symbol and return a symbol whose section/value has changed.
  2. moves the post-finalizeSections assignAddress() inside the loop of finalizeAddressDependentContent() and makes it iterative. Symbol assignment may not converge so we make a few attempts before bailing out.

Note, assignAddresses() must be called at least twice. The penultimate
call finalized section addresses while the last finalized symbol values.
It is somewhat obscure because there was no comment.
linkerscript/addr-zero.test tests this.

Event Timeline

MaskRay created this revision.Aug 15 2019, 2:22 AM

I think that this is close. I've got some concerns about the interaction of convergence limits, and it may be worth investigating if it is possible to make a separate symbol update pass that runs after addresses have stabilized.

I think it will be worth adding a test to make sure that the bail out does indeed occur. Something like:

sym1 = sym2
sym2 = sym3
sym3 = sym4
sym4 = sym5
sym6 = sym7
sym8 = .

I'm happy to work on a thunk creation test that takes quite a few iterations to converge.

ELF/Writer.cpp
1571

The thunks code already has a converge limit of 10, I think it would be possible to create a test case that had a single assignment say sym = . that was after a code section that would vary in size due to Thunk creation. If the code section converged within 10 but not within 5 then we'd get an error. I think if the symbol convergence test is within this loop then we should probably extract the convergence test out of ThunkCreation, or at least have some way of synchronizing all the convergence limits.

Writing a thunk test that doesn't converge isn't difficult, writing one that takes many iterations to convergence is somewhat tedious. I can help write one as I've done a few before.

1595

To follow on from the previous comment about convergence errors in Thunks, if we choose to keep the convergence tests separate so we know which part isn't converging (if that is even possible) then it might be worth moving the tries and error message into script and assignAddresses() to keep this loop clean.

1602

An argument could be made that testing for convergence of symbols could/should be done after the final addresses have stabilised. I don't think that there is a legal linker script that could be made where assigning to symbols in a linker script should affect the convergence of thunks, patches and partitions. Doing the symbol assignment with stable addresses would avoid the clashing convergence limit problem.

My initial thought was to see if just a symbol assignment update could be run here, without going through the complexity of assignAddresses() but that would definitely need some thought.

MaskRay marked an inline comment as done.Aug 15 2019, 3:27 AM
MaskRay added inline comments.
ELF/Writer.cpp
1571

This is a bit different. The return value of script->assignAddresses(); does not affect changed, i.e. before thunks converge (changed becomes false) tries should not decrease.

script->assignAddresses is executed at least twice, without or with this patch. This is a bit awkward, but if I change the logic here to:

for (;;)
  assignAddresses();
  createThunks();
  if (!changed) break;

test/ELF/linkerscript/addr-zero.test added by @grimar's D55550 will break.

foo = ADDR(.text) - ABSOLUTE(ADDR(.text));

Ideally we don't have to call assignAddresses twice.

Writing a thunk test that doesn't converge isn't difficult, writing one that takes many iterations to convergence is somewhat tedious.

Yes, a test involving both non-trivial symbol assignment and non-trivial thunk will be very useful... Thanks in advance.

MaskRay updated this revision to Diff 215364.Aug 15 2019, 3:33 AM

Add a non-convergence test expr-converge2.test and improve expr-converge.test

MaskRay updated this revision to Diff 215374.Aug 15 2019, 5:50 AM
MaskRay edited the summary of this revision. (Show Details)

Improve test
Add a comment why the two calls of assignAddresses() are written this way.

MaskRay updated this revision to Diff 215377.Aug 15 2019, 5:55 AM

bug fix: return sym; -> changed = sym;

MaskRay added a comment.EditedAug 15 2019, 6:31 PM

Investigated a bit how ld.bfd works.

SECTIONS {
  . = 0x1000;
  a = b + 1; b = c + 1; c = d + 1; d = e + 1; e = f + 1; f = g + 1; g = h + 1; h = .;
}
// ld/ld-new -T a.lds a.o -o a
// undefined symbol `b' referenced in expression

SECTIONS {
  . = 0x1000;
  a = b + 1; b = c + 1; c = d + 1; d = e + 1; e = f + 1; f = g + 1; g = .;
}
// st_value(a) is incorrect 6, not 0x1006.

// st_value(a) is correct (0x1005) with one less variable.

In either case, lang_do_assignments ran at least 3 times.

  • lang_do_assignments (lang_mark_phase_enum); // in ld/ldlang.c:lang_process
  • lang_do_assignments (lang_assigning_phase_enum); // in ld/ldlang.c:lang_relax_sections
  • lang_do_assignments (lang_final_phase_enum); // in ld/ldlang.c:lang_process

The initial 3 calls allow it to compute a slightly longer chain, though a new lang_do_assignments (lang_assigning_phase_enum); only allows it to compute the case with one more variable. I observe that the aarch64 port calls lang_do_assignments 4 times. This is because ld/emultempl/elf-generic.em:gld${EMULATION_NAME}_map_segments (bfd_boolean need_layout) calls lang_relax_sections (need_layout); twice.

In lang_relax_sections, the symbol assignment phase is followed by lang_size_sections. Our script->assignAddresses() should match its behavior well.

void
lang_relax_sections (bfd_boolean need_layout)
{
...
  if (need_layout)
    {
      /* Final extra sizing to report errors.  */
      lang_do_assignments (lang_assigning_phase_enum);
      lang_reset_memory_regions ();
      lang_size_sections (NULL, TRUE);
    }
}

In finalizeAddressDependentContent(), we could extract the symbol assignment iteration and do it separately after the layout is fixed, but that would require more code.

I've created D66346 which maxes out the permitted Thunk convergence limit. I've done it as Arm rather than AArch64 as the range limits are lower on Arm. This should be sufficient to test that if there is any interaction between convergence limits. Apologies for the delay in putting it together.

MaskRay updated this revision to Diff 215626.Aug 16 2019, 9:43 AM

Change tests to adapt D66346

ruiu added inline comments.Aug 19 2019, 1:00 AM
ELF/Writer.cpp
1576

I believe this line is executed only when you give pathetic object files to the linker, but we still probably have to use error to make it work better for the embedding use case.

MaskRay updated this revision to Diff 215830.Aug 19 2019, 1:23 AM
MaskRay marked an inline comment as done.
  • fatal("thunk creation not converged");

+ error("thunk creation not converged");
+ break;

Thanks for the update. Have been thinking in the back of my mind if there were any other way of solving the problem without needing to iterate. The only thing I can think of right now is some kind of analysis that, for want of a better word, topologically sorts expressions so that there are no forward references, with an error message if this isn't possible. This could get complicated as there is limited scope to move or reorder assignments in OutputSections. Other than that I've not got any more comments at the moment.

ELF/LinkerScript.cpp
1067

It might be worth extracting this and the check below into functions. Something like:

oldValues = getSymbolAssignmentValues(sectionCommands);
...
return findChangedSymbol(oldValues);

Not a strong opinion though.

ELF/Writer.cpp
1570–1571

This comment won't be true anymore, depending on linker scripts.

MaskRay updated this revision to Diff 215853.Aug 19 2019, 3:30 AM
MaskRay marked 2 inline comments as done.

Delete a stale comment
Extract out getSymbolAssignmentValues

Thanks for the update. Have been thinking in the back of my mind if there were any other way of solving the problem without needing to iterate. The only thing I can think of right now is some kind of analysis that, for want of a better word, topologically sorts expressions so that there are no forward references, with an error message if this isn't possible. This could get complicated as there is limited scope to move or reorder assignments in OutputSections. Other than that I've not got any more comments at the moment.

Unfortunately linker scripts are not in a single static assignment form... = and += can appear multiple times. Such analysis will be difficult. According to my experiments (see prior comments), ld.bfd's evaluation strategy is quite similar to: run assignment statements one by one, but repeat a few times, where the repetition count depends on layout convergence. It doesn't wait for symbol assignments to converge, but it evaluates the assignment statements more than we current do. Thus it can correctly evaluate some simple forward declaration forms. I think the approach we use in this patch should capture its strategy quite well. This is probably sufficient for most forward declarations we may encounter in practice.

ELF/LinkerScript.cpp
1067

I'll do:

oldValues = getSymbolAssignmentValues(sectionCommands);
...
for (auto &it : oldValues) { /// this part is not too complex now, so i'll inline it
  ...
}
return changed;

🎡Ready to roll!

I'm happy with this as it stands. It should help prevent problems coming from alterations to the linux kernel's linker script and also help others migrating from ld.bfd. With luck we'll be able to build on this to fix the symbol type problem in https://bugs.llvm.org/show_bug.cgi?id=42506

ruiu accepted this revision.Aug 26 2019, 2:47 AM

LGTM

ELF/LinkerScript.cpp
1054

This needs a function comment.

This revision is now accepted and ready to land.Aug 26 2019, 2:47 AM
MaskRay updated this revision to Diff 217102.Aug 26 2019, 3:09 AM

Move getSymbolAssignmentValues above because it might be used by processSymbolAssignments in the future.

add a function-level comment

Add getChangedSymbolAssignment

MaskRay updated this revision to Diff 217103.Aug 26 2019, 3:20 AM

vector -> const vector &

This revision was automatically updated to reflect the committed changes.