IFUNC resolver scheduling (bugs 21041, 20019)

[Florian Weimer]

On 01/26/2017 02:37 AM, Carlos O'Donell wrote:
> On 01/25/2017 08:57 AM, Florian Weimer wrote:
>> I tried to fix most of the issues involving IFUNC resolvers and their
>> access to unrelocated symbols.
>
> Thank you very much for tackling this somewhat complicated topic.
>
> Like the issue of constructors and destructions, IFUNC is not a trivially
> black and white issue, and some trade-offs need to be made.
>
>> My first attempt (on branch fw/bug21041) records all relocations
>> against IFUNC resolvers during elf_machine_rela processing, and adds
>> another pass to apply them.
>
> I like this design. It's relatively straight forward to understand,
> audit and maintain.
>
>> The general approach is to execute IFUNC resolvers
>> deepest-dependency-first (based on the object in which the IFUNC
>> resolver resides, not the relocation which references it).  Most of
>> the time, this ensures that IFUNC resolvers do not encounter
>> unrelocated symbols because IFUNC resolvers from their dependencies
>> have already executed, patching in the missing relocation.  Symbol
>> interposition can still bypass that, though.
>
> Is there a problem with symbol interposition?

Symbol interposition can make available to IFUNC resolver function 
definitions which reside in objects which have not been fully relocated 
yet.  This is what happens in the initial test case for bug 21041 
(libpthread interposes longjmp).  Delaying IFUNC relocations should fix 
this particular test case because the non-IFUNC relocations for 
libpthread are processed before the IFUNC resolver in libpthread runs. 
But is not a general solution to this kind of problem.

>> The branch is currently slightly buggy because it reverses the order
>> of relocation processing within the same object, and it does not
>> delay copy relocations, so those could copy unrelocated data.
>> (Support for copy relocations whose source address is determined by
>> an IFUNC resolver is missing as well, but this is a separate matter
>> and quite easy to fix.)
>
> I don't think there is any real bug in reversing the order of the
> IRELATIVE relocation handling.  What matters more is that other
> earlier listed relocations are completely handled in order that the
> resolver function may run correctly (where possible, and if not possible
> then at least deterministic).

Right.  It might still be beneficial to process these relocations in 
increasing order.

> Isn't delaying copy relocations and support for copy relocations whose
> source address is determined by an IFUNC resolver the same thing?

No, I don't think so.

The latter is simply a missing switch case in the handler for delayed 
IFUNC processing.  The former is a relocation ordering issue.

>> Support for DT_TEXTREL is currently missing, too.  This needs another
>> preparatory patch like the one to delayed RELRO activation.  (For
>> dlopen, the RELRO activation delay does a bit too much work because
>> it mprotects everything again, not just the newly allocated
>> objects.)
>
> DT_TEXTREL shouldn't be too different, just filling the right pieces
> given the framework you already have in place?

Yes, it's similar to RELRO processing.

> I think Szabolcs makes a good point here, in that we should consider:
>
> * What is the cost of a second walk?

I fear it is substantial.  I'm attaching some crude scripts which I used 
to gather statistics.

For example, I get this for /bin/bash:

Section '.rela.dyn' contains 2512 relocations:
   19 IFUNC relocations from index 2294 to 2496, interval size 203 (92.3%)
   7 COPY relocations from index 2505 to 2511, interval size 7 (0.3%)

In general, we typically have 10% of relocations which we have redo per 
object.  But if we look at only those relocations which require symbol 
lookup, the percentage is much higher (92.3% in the bash example).

The main problem with the two-pass approach is that there is no place 
where it can cache symbol lookup results.  If we assume that relocation 
performance is dominated by symbol lookups (which is reasonable IMHO), 
we are looking at a very substantial performance hit for the two-pass 
approach.  Some of the performance hit could be avoided if we installed 
a magic function pointer as a temporary relocation result, and skip 
relocations which are not equal to that magic value on subsequent passes.

The next problem is that it's not actual two-pass.  We'd need a separate 
pass for each IFUNC provider/consumer pair, I think.  Otherwise, we 
would not perform IFUNC relocations in depth-first order anymore.

> * What is the cost of only recording only that IRELATIVE relocs exist
>   (recording the first one) and then starting the walk from there?

IRELATIVE relocations are very rare because you need symbol visibility 
management and IFUNCs in the same object.  libc.so.6 has 8 of them. 
Some of them are likely accidents and unintentional.  I'm not sure if 
they are a good target for optimization.

>> The combreloc feature sorts relocations of the same type together.
>> The static linker could sort relocations involving IFUNCs together,
>> and we could recognize this in the dynamic linker and record spans of
>> relocations instead individual relocations.  This would reduce the
>> number of delayed relocation records we'd have to allocate.
>
> This is exactly what POWER does for OPD-related relocs (Alan Modra
> explained this to me once).
>
> I think this would be a reasonable optimization, but it's just that,
> an optimization. Since you can always record the first record, and
> start the walk there for the given object?

It's a very important optimization because it ensures we only re-do the 
symbol lookups we absolutely have to do.  Even if we have the optimized 
symbol ordering, a newly added IFUNC could easily cause a 25% 
performance hit for relocation processing because the symbol range is 
much larger again.

Thanks,
Florian
-------------- next part --------------
A non-text attachment was scrubbed...
Name: list-ifunc-symbols.sh
Type: application/x-shellscript
Size: 168 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20170126/4d5daf5a/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: find-ifunc-ranges.py
Type: text/x-python
Size: 3164 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20170126/4d5daf5a/attachment.py>