[Bug binutils/29993] objcopy --merge-notes slow for large .so with many annobin notes

[fche at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=29993

--- Comment #5 from Frank Ch. Eigler <fche at redhat dot com> ---
I have not previously looked into the annotation notes in great detail, so am
working from a tyro understanding of
https://fedoraproject.org/wiki/Toolchain/Watermark .   Please excuse my naivite
with the following:

- The "merging the notes, following rules must be observed" list of that wiki
page is lacking rationale.  Any transformation that meets the specifications
set in the previous paragraphs should be fine.

- For example, "Preserve any NT_GNU_BUILD_ATTRIBUTE_FUNC notes" can't be right.
 Previous to --merge-notes, there are millions of these "func" notes in
libxul.so, but after, only a few dozen.  (Yes, it turns out there are hundreds
of thousands of merges occurring, so that inner loop does likely run many more
than 16 iterations.)

- For example, "Preserve the ordering of the notes" can't be that serious if
the previous prose indicates entries cannot be assumed to be sorted by address,
nor can the special version tags be assumed to be at the front.

So, as for a more efficient merging algorithm, I would explore something like
this:

1) First pass: load all the notes of the bfd, sort them by start-address,
grouping them into separate lists (by attribute "owner", "value", "type"). 
This is so that each list consists of exactly those entries that could be
merged, based on the entries' address ranges.

2) For each of those note group lists:
2a)  Create an output list for the new merged notes in this group.
2b)  Iterate entries by address.
2b1)     Copy the current entry into the output list.  We'll merge others into
this one.
2b2)     If the next entry adjoins/overlaps this entry, merge the start/end
range of the new entry.  Try this again for subsequent entries until finding
one that does not adjoin/overlap.  Mark that next entry as the next one for
iteration at step 2b)
3)  Write the output lists into the output elf file, replacing the previous
.gnu.build.attributes.

This should be O(N log N) time algorithm for sorting by address, then O(N) for
the actual merging process.

-- 
You are receiving this mail because:
You are on the CC list for the bug.