Page MenuHomePhabricator

[MachO] Implement -order_file as a separate ordering pass.
Needs ReviewPublic

Authored by ruiu on Jan 27 2015, 2:15 PM.

Details

Reviewers
kledzik
Summary

On Mac OS you can pass a text file as an argument for -order_file
command line option. That file contains a list of symbols, and the
linker sorts these symbols in the same order as in the order file.

That custom ordering was implemented by adding a "custom" comparator
function to the LayoutPass. That made the comparator function in the
LayoutPass, which does too much stuff already, more complex.

I'm trying to make the pass simpler and faster. I found that if we
implement the feature as a separate pass, it becomes easy to understand.

In this patch, I added a new pass, OrderPass, which sorts atoms
according to the order file. Because it uses stable sort, it preserves
symbol order if they are not mentioned in the order file. We already
took similar approach in PE/COFF (PECOFF/GroupSectionPass.h).

This patch has no change in functionality.

Diff Detail

Event Timeline

ruiu updated this revision to Diff 18853.Jan 27 2015, 2:15 PM
ruiu retitled this revision from to [MachO] Implement -order_file as a separate ordering pass..
ruiu updated this object.
ruiu edited the test plan for this revision. (Show Details)
ruiu added a reviewer: kledzik.
ruiu added a project: lld.
ruiu added a subscriber: Unknown Object (MLST).
kledzik edited edge metadata.Jan 27 2015, 2:52 PM

There maybe lots of other parts of this LayoutPass that mach-o needs but ELF does not. Why not just prune away at this until you get pass that is fast enough for ELF. Then split this in to two passes. One for mach-o and one for ELF, and let the drivers choose the pass to use.

ruiu added a comment.Jan 27 2015, 3:07 PM

My understanding is that in all architectures we basically want to sort atoms in the same order as they are ordered in the command line (file order and then in-file order). I looked at the history of the LayoutPass and found that the pass actually did that before. I think we want to restore that behavior, and apply that pass for all archs.

Each arch then optionally run a pass to (stable-) sort atoms after the LayoutPass to tweak the sort result.

I think this separation should work for all architectures and I think this separation is clean and nice.

Sure two passes is conceptually clean, but if it turns out that running sort() twice for mach-o makes linking slower for mach-o than it currently is, then that is not ideal.

The other way would be to have one layout pass that uses a base class for the comparator which the ELF layout pass uses as-is, but there is a (non virtual) way for mach-o to supply a more complex comparator (today's comparator).

ruiu added a comment.Jan 27 2015, 4:40 PM

I feel that discussing performance on the two-pass solution at this point
could lead to a premature optimization> Maybe we should run a benchmark to
see if it's going to be a real issue. Second sort can be faster than first
sort because second sort sorts a mostly-sorted array. But sure, sort is
O(log n). Run that stuff twice is not optimal. We may want to avoid that if
possible.

I carefully read the code for ELF and found that the functionality that the
LayoutPass provides is overkill for that architecture. We don't need that
amount of code.

Currently the LayoutPass is applied unconditionally to all architectures.
Maybe we should stop doing that and let each arch to define its own layout
pass. The current LayoutPass can be simplified to <10 lines of code, so it
wouldn't worth abstracting.

Leaving this pass as-is and adding a new simple pass that ELF (and maybe COFF) uses instead is fine with me.

ruiu added a comment.Jan 27 2015, 5:32 PM

If you want that way, that works for me too. But could you elaborate a bit on which part of the the LayoutPass Mach-O needs? I don't expect Mach-O needs all features that the pass provides.

All those comparisons in compareAtomSub() are part of the system linker on darwin. See:

http://www.opensource.apple.com/source/ld64/ld64-123.2.1/src/ld/passes/order_file.cpp
ruiu added a comment.Jan 27 2015, 5:56 PM

I see. Thanks for the pointer! I now understood that that ordering is needed.

From that file, it looks to me that it doesn't need "sort by lc._override an rc._override if both rhs and lhs are in the same layout-after chain" feature. The file actually consists of the code to prepare for that comparison.

This needs to be part of LayoutPass, as its something that I wanted to add to the Gnu flavor too.

ruiu added a comment.Jan 28 2015, 10:52 AM

Why? If you think we need a feature, please at least briefly explain why we
need that, too.

Several of our customers want this functionality of ordering functions/data(without linker scripts) to just take an order file and order them appropriately.

ruiu added a comment.Jan 28 2015, 11:27 AM

Currently there's no way to specify symbol orders. If someone wants to
reorder symbols in a special manner, one needs to use LLD as a library and
write a custom pass to enforce some specific ordering. That means they can
reorder symbols in their pass, rather than doing tricky things with layout
references and let the LayoutPass to sort them. The LayoutPass is
overdesigned and hard to use. Let's not depend on that too much.