Re: Plan for incremental linking with gold

[Daniel Jacobowitz <drow at false dot org>]

Just some thoughts; I hope they're useful.

On Tue, Dec 23, 2008 at 06:30:23PM -0800, Ian Lance Taylor wrote:
> For additional flexibility, the options --incremental-changed and
> --incremental-unchanged may be used.  Every input file which appears
> between --incremental-changed and --incremental-unchanged will be
> assumed to have not changed since the last incremental link.  This may
> be used by build systems which have extra knowledge about which files
> have changed.

Is there an extra negative in this description, or are changed and
unchanged swapped?  ISTM that you'd want --incremental-changed,
--incremental-unchanged and --incremental-unknown (or default).

Would you have to wrap each changed or unchanged file without changing
order?  Since if you do change the link order the binary could be
semantically different.  But incremental linking can reorder anyway,
so it would be better to identify order-sensitive sections in the
linker.  Or order-insensitive sections, I suppose; glibc has custom
section names which are order sensitive, IIRC.

> These restrictions could be sometimes avoided with some additional
> work.  However, they are not the most important case, and the
> algorithm is considerably simplified if we do not have to consider
> changes to symbol overriding.

I wrote an incremental linker several years ago.  The goals were
different than in gold; it was designed to produce binaries with
minimal deltas, for binary patching of deployed systems.  So it was
worth it to work a bit harder at link time to reduce delta; we
measured success in the unchanged proportion of the binary.  Handling
symbols which moved from one file to another was tricky.  As you've
written below this is similar to adding or removing a file.  The
problem I ran into was that this happens for COMDAT groups
corresponding to potentially inlined functions.  They appear or
disappear at the compiler's whim, so support for this was pretty much
mandatory.  For the sort of C++ code that you're probably concerned
with at Google, I'd expect this to make a big impact.

Another piece that gave me a lot of trouble was changes in
requirements for linker-constructed sections like the PLT.  The PLT is
traditionally in front of .text; this means that if the new binary
requires more PLT entries than the old one, everything moves.
In gold you'll have the freedom to fall back to a new link at that
point, but it's preferable not to.  You require --incremental on the
first link, right?  It might help to allocate some extra space for
linker-generated sections to increase the chances of success later,
similarly to segments.

Naturally there's a range of thoroughness you can apply here; for
highest success (measured in terms of unchanged bytes in the output
binary) you want to leave PLT entries where they were when possible.
The program headers are also up front; if you want to add segments
without moving .text, it helps to leave space for at least two extra
PT_LOAD's (text and data).

We did similarly for sections; added some padding around sections
likely to change (not applicable for gold's goals) so that they could
grow in place.  We also kept track of holes in the binary caused by
decreased section size to fill things in later without excessive code
growth; I see that in your plans already.

Maybe some day a similar mode (--incremental-thorough?) can be added
to gold.  I might be able to get permission to release the code if
you're interested; let me know.

>   * If archive:
>     + Treat each member as a changed file.

Should be trivially easy to do better than this?  ar has timestamps.

>   * If linker script:
>     + Recompute everything.

It's not appropriate for your goals, but there's ways around this; it
just complicates layout a bit.  You need to be able to answer the
question "does this placement violate the new linker script".
Fortunately I was using ARM's scatter-loading files at the time; a
strict interpretation of GNU linker script format does not give the
linker a lot of freedom to reorganize.  I think this is a drawback of
the current format.  If I ever find time to hack on gold for embedded
use, I've been thinking about adding a simpler format that leaves the
linker more freedom.

> Handling debugging information which changes size may require
> modifications to gdb to support non-contiguous debugging information.
> (Or maybe we will just always put the debugging information at the end
> of the file).

Have you considered leaving debug info in object files, as Apple does?
With this --incremental designed for development use only, packaging
is less of a problem.

-- 
Daniel Jacobowitz
CodeSourcery