[PATCH 00/59] Deduplicating CTF linker
Nick Alcock
nick.alcock@oracle.com
Tue Jun 30 23:30:47 GMT 2020
So the deduplicating CTF linker is finally ready for review. (Note: ready
for *review*, probably not yet quite ready for committing, since to speed
things up a bit I've posted before all non-Linux-arch tests are finished.
In particular, big-endian tests, Solaris tests, and tests on mingw and
cygwin will be done in parallel with this review. Cross build-and-checks to
every supported arch, --enable-targets=all tests, and 64-bit and 32-bit
tests on x86-64 Linux and FreeBSD have been done already.)
Please read and review as you wish -- most of these are libctf-only changes,
but I'd be very happy for review of those too. There are only a few dozen
lines of non-testsuite changes outside libctf.
Before the actual linker changes comes a lot of loosely-related stuff in
libctf.
First, there's new infrastructure, mostly used by the deduplicating linker
but also to improve interaction with the linker itself and other consumers,
like GDB:
- proper textual error/warning reporting (adopted by all in-binutils
consumers): libctf errors are no longer just an errno value and an error
message swallowed up in the debug stream
- adding new error codes only needs to be done in one place, and produces
fewer relocs in the final binary
- new API functions to get things we were concealing before, like the
number of members in an enum, or to do things previously impossible,
like bump the refcount on a ctf_file_t so you can hold it open for
longer, and a bunch of new API functions for the dynhash
- a new dynhash-like thing, the dynset (doesn't store a value, but is
much more memory-efficient), still based on the libiberty hashtab
- a whole new type of iterator, the *_next iterator family, much easier
to use than the existing *_iter iterators that take a callback: I hope
to move away from use of the old *_iter functions in most cases within
libctf, and eventually reimplement *_iter in terms of *_next
Then there are a lot of bugfixes, and performance and memory-usage improvements,
again mostly triggered by the needs of the deduplicator.
Once those are past we have linker-related changes, starting on patch 43,
including one big commit (patch 50) containing the CTF deduplicator itself.
(I can cut this one up if you find it too big, but control roughly flows
from the top of the patch to the bottom anyway, so slicing it into pieces
doesn't really buy much in terms of readability.)
Nearly all the changes are in libctf: ld gets only a couple of new options
to control various new CTF linker settings and a better way of reporting
(arbitrarily many) libctf errors and warnings. No changes are needed in
libbfd at all.
Most of the new work is in the new file libctf/ctf-dedup.c, which
deduplicates the types section of CTF dicts, taking a bunch of CTF dicts and
linking them together into a single output dict and possibly a set of child
dicts containing conflicting types and (link mode allowing) types that
appear in only one input dict. This gets done by recursively hashing types
(terminating the recursion at tagged structures and unions so as not to get
caught in cycles), identifying types with ambiguous definitions (multiple
hash values for the same name), then emitting one type per deduplicated type
hash value into appropriate output dicts. The algorithm used by ctf-dedup.c
is documented at the top of the file.
The changes in ctf-link.c tie that deduplicator into the rest of libctf, fix
bugs in the existing variable-section linking code, allow the variable
section to be omitted from the output, allow CTF dicts to be opened lazily
by libctf itself rather than requiring callers to do it, start using the new
err/warning infrastructure, and fix a bunch of bugs.
There is a new configure option which turns on debug output during the
initial type hashing phase: this generates so very much output that it
massively slows ld down even when LIBCTF_DEBUG is not set in the
environment. So it's turned off by default. When that configure flag is
not provided, CTF-related operations are not at all the slowest thing ld
does, even though the deduplicator is still serial (though deduplication can
still take a few seconds for bigger projects): see below for some example
timings, some of which are approximate because the timings are frankly in
the noise. Deduplication *is* a bit memory-hungry, mostly due to hashtab
overhead, but again this is tolerable and will be reduced further in time.
ld gains new options to customize the link mode (share-unconflicted or
share-duplicated: see ld.texi for the meaning of this) and to emit the
variable section if desired. (Normal links will not want a variable
section, because the things in there correspond to static variables that
have no symbol table entry and cannot be looked up in any useful fashion.)
There is also a new CTF ld testsuite, largely due to Egeyar Bagcioglu: it
tests linking of CTF sections (including conflicting type names in different
TUs landing in suitable child dicts) and operation on a bunch of invalid
inputs: binutils gets some formatting fixes and an enhancement to
run_dump_test to let it compile things before assembling them.
Unfortunately because the pseudos GCC generates to emit assembler output are
often nonportable, the testsuite works by compiling C into asm and then
assembling and linking that: so a compiler capable of CTF generation via -gt
is needed to run the new tests. We hope to fix this in time, but it will
take GCC changes.
Finally there is an important bugfix: our trick to ensure that the output
has only one .ctf section broke sometime in the last six months or so of
upstream development, so we were getting outputs with huge numbers of empty
CTF sections in: the new approach should be more robust.
I am reasonably confident in the algorithm, though no doubt bugs will
emerge. CTF file format changes should not require significant changes in
the deduplicator, because we try wherever possible to use the public libctf
API in the dedup code rather than digging into the guts of the file format.
Much of this is probably reusable when CTF is extended to handle other
languages, as well (e.g. we don't really depend on any particular detail of
the C type system to break cycles, only that there *is* some thing or set of
things which must be present in order for a cycle in the type graph to
exist).
Coverage analysis suggests that the tests now in the testsuite cover all of
ctf-dedup.c except for paths associated with ld -r (input dicts with
children), paths associated with types that CTF cannot represent, a couple
of lines associated with cu-mapped links, and paths associated with the
share-duplicated link mode: perhaps 80% of the total line count is covered.
More tests will be added later to cover the missing cases.
Some speed (cpu-user-time) and CTF size figures are below: they were taken
on my 2.4GHz x86-64 Linux workhorse box. The GCC used was a GCC 10 snapshot
from mid-Feb plus CTF-generation patches: see
https://github.com/oracle/gcc.git oracle/ctf-gen (if you want to replicate
this but don't want to fetch from GitHub I have a git bundle from upstream
commit 7a775242ea296849a34ce27de179eaaec411e880 available at
<http://www.esperi.org.uk/~nix/bundles/gcc-ctf.bundle>).
We start with easy stuff and proceed to things with crazy numbers of types
or that do mad things in the build process as a bit of a regression test,
notes below. Sorry this is over 80 chars wide: I hope it's readable anyway:
Program DWARF size .ctf size Time[3]
[1] Compressed Uncompressed Largest -gt no -gt
(no strings) input TU
GNU ld 1150314 42479 146945 63623 142226 17.33 16.76
libbfd 2746704 71380 237445 129929 143970 43.25 41.61
ld (static) 4490908 86428 289947 170933 162226 59.72 58.0
gas 1063842 48537 161929 75643 148271 17.66 16.66
coreutils ls 164517 6455 19384 15673 18481 0.30 0.33
vim 4740693 111080 372398 281471 138455 176.21 175.46
libX11 9525236 45799 155109 125534 58964 300.11 298.40
emacs 26.3 [2] 8079794 86267 303306 225828 174808 938.52 933.78
GhostScript 18972151 2311683[4] 4828538 2726368 127543 265.73 252.41
Gtk 3.24.20 11895771 255101[5] 908719 717034 255101 1268 1245
CLISP[6] 2870363 49234 193162 124811 254536 160.90 151.42
X.org xserver 6718404 105955 369395 295470 257878 448 436
[1] .debug_info only: perhaps I should include .debug_str? Really what we
need is "type only" DWARF for comparison, but that requires compiler
hacking I haven't looked at yet.
[2] times include all lisp compilation
[3] times do not include configury: a good few of them are in the noise.
This at least shows that the deduplicator won't slow things down too
badly.
[4] GhostScript is a worst case for huge numbers of types with identical
names but distinct definitions in different TUs. Format v4 gains the
ability to share the definitions of such types between TUs, and will
reduce this size back down to something more like the size of the main
dict, 113983 bytes. (The deduplicator will hardly need to change: the
changes are elsewhere in libctf.)
[5] Slightly afflicted by the same things as GhostScript: the CTF size will
probably halve in format v4.
[6] size of lisp.a's sole member: clisp is an oddball, and would probably
require a specialized reader that knew something about the .mem dumping
process.
Egeyar Bagcioglu (3):
libctf, types: ensure the emission of ECTF_NOPARENT
ld: Reformat CTF errors into warnings.
ld: new CTF testsuite
Nick Alcock (56):
include, libctf: typo fixes
libctf: restructure error handling to reduce relocations
libctf, create: support addition of references to the unimplemented
type
libctf, create: do not corrupt function types' arglists at insertion
time
libctf, create: add explicit casts for variables' and slices' types
libctf, types: allow ctf_type_reference of dynamic slices
libctf, open: drop unnecessary historical wart around forwards
libctf, create: member names of "" and NULL should be the same
libctf, create: fix addition of anonymous struct/union members
libctf, create: empty dicts are dirty to start with
libctf, types: support slices of anything terminating in an int
libctf, types: ints, floats and typedefs with no name are invalid
libctf, archive: stop ctf_arc_bufopen triggering crazy unmaps
libctf: having debugging enabled is unlikely
libctf: add ctf_type_name_raw
libctf: add ctf_type_kind_forwarded
libctf: add ctf_member_count
libctf: add ctf_archive_count
libctf: fix __extension__ with non-GNU C compilers
libctf: add new dynhash functions
libctf, hash: improve insertion of existing keys into dynhashes
libctf, hash: save per-item space when no key/item freeing function
libctf, hash: introduce the ctf_dynset
libctf: move existing inlines into ctf-inlines.h
libctf: add ctf_forwardable_kind
libctf: add ctf_ref
libctf, next: introduce new class of easier-to-use iterators
libctf, next, hash: add dynhash and dynset _next iteration
libctf: pass the thunk down properly when wrapping qsort_r
libctf: error out on corrupt CTF with invalid header flags
libctf, ld, binutils: add textual error/warning reporting for libctf
libctf, types: enhance ctf_type_aname to print function arg types
libctf, decl: avoid leaks of the formatted string on error
libctf, dump: migrate towards dumping errors rather than truncation
libctf, dump: fix slice dumping
libctf, open: fix opening CTF in binaries with no symtab
libctf, archive: fix bad error message
libctf: check for vasprintf
libctf: rename the type_mapping_key to type_key
libctf: sort out potential refcount loops
libctf: drop error-prone ctf_strerror
libctf, link: add lazy linking: clean up input members: err/warn
cleanup
libctf, link: fix ctf_link_write fd leak
libctf, link: redo cu-mapping handling
ctf, link: fix spurious conflicts of variables in the variable section
libctf, link: add the ability to filter out variables from the link
libctf: add SHA-1 support for libctf
libctf, dedup: add new configure option --enable-libctf-hash-debugging
libctf, dedup: add deduplicator
libctf, link: add CTF_LINK_OMIT_VARIABLES_SECTION
libctf, link: tie in the deduplicating linker
binutils: objdump: ctf: drop incorrect linefeeds
ld: new options --ctf-variables and --ctf-share-types
binutils, testsuite: allow compilation before doing run_dump_test
ld, testsuite: only run CTF tests when ld and GCC support CTF
ld: do not produce one empty output .ctf section for every input .ctf
binutils/objdump.c | 25 +-
binutils/readelf.c | 23 +-
binutils/testsuite/lib/binutils-common.exp | 58 +-
include/ctf-api.h | 178 +-
include/ctf.h | 3 +-
ld/Makefile.am | 7 +-
ld/Makefile.in | 8 +-
ld/NEWS | 10 +
ld/configure | 6 +-
ld/configure.ac | 1 +
ld/ld.h | 8 +
ld/ld.texi | 34 +
ld/ldlang.c | 63 +-
ld/ldlex.h | 3 +
ld/lexsup.c | 29 +
ld/testsuite/ld-ctf/A-2.c | 6 +
ld/testsuite/ld-ctf/A.c | 5 +
ld/testsuite/ld-ctf/B-2.c | 5 +
ld/testsuite/ld-ctf/B.c | 4 +
ld/testsuite/ld-ctf/C-2.c | 5 +
ld/testsuite/ld-ctf/C.c | 5 +
ld/testsuite/ld-ctf/array-char.c | 2 +
ld/testsuite/ld-ctf/array-int.c | 1 +
ld/testsuite/ld-ctf/array.d | 34 +
ld/testsuite/ld-ctf/child-float.c | 4 +
ld/testsuite/ld-ctf/child-int.c | 4 +
ld/testsuite/ld-ctf/conflicting-cycle-1.B-1.d | 40 +
ld/testsuite/ld-ctf/conflicting-cycle-1.B-2.d | 41 +
.../ld-ctf/conflicting-cycle-1.parent.d | 38 +
ld/testsuite/ld-ctf/conflicting-cycle-2.A-1.d | 40 +
ld/testsuite/ld-ctf/conflicting-cycle-2.A-2.d | 41 +
.../ld-ctf/conflicting-cycle-2.parent.d | 40 +
ld/testsuite/ld-ctf/conflicting-cycle-3.C-1.d | 39 +
ld/testsuite/ld-ctf/conflicting-cycle-3.C-2.d | 40 +
.../ld-ctf/conflicting-cycle-3.parent.d | 37 +
ld/testsuite/ld-ctf/conflicting-enums.d | 35 +
ld/testsuite/ld-ctf/conflicting-typedefs.d | 33 +
ld/testsuite/ld-ctf/cross-tu-1.c | 12 +
ld/testsuite/ld-ctf/cross-tu-2.c | 8 +
ld/testsuite/ld-ctf/cross-tu-conflicting-2.c | 8 +
ld/testsuite/ld-ctf/cross-tu-cyclic-1.c | 14 +
ld/testsuite/ld-ctf/cross-tu-cyclic-2.c | 16 +
ld/testsuite/ld-ctf/cross-tu-cyclic-3.c | 3 +
ld/testsuite/ld-ctf/cross-tu-cyclic-4.c | 4 +
.../ld-ctf/cross-tu-cyclic-conflicting.d | 57 +
.../ld-ctf/cross-tu-cyclic-nonconflicting.d | 50 +
ld/testsuite/ld-ctf/cross-tu-into-cycle.d | 64 +
ld/testsuite/ld-ctf/cross-tu-noncyclic.d | 46 +
ld/testsuite/ld-ctf/ctf.exp | 31 +
ld/testsuite/ld-ctf/cycle-1.c | 7 +
ld/testsuite/ld-ctf/cycle-1.d | 36 +
ld/testsuite/ld-ctf/cycle-2.A.d | 40 +
ld/testsuite/ld-ctf/cycle-2.B.d | 40 +
ld/testsuite/ld-ctf/cycle-2.C.d | 40 +
ld/testsuite/ld-ctf/diag-ctf-version-0.d | 5 +
ld/testsuite/ld-ctf/diag-ctf-version-0.s | 44 +
.../diag-ctf-version-2-unsupported-feature.d | 5 +
.../diag-ctf-version-2-unsupported-feature.s | 44 +
ld/testsuite/ld-ctf/diag-ctf-version-f.d | 5 +
ld/testsuite/ld-ctf/diag-ctf-version-f.s | 44 +
ld/testsuite/ld-ctf/diag-cttname-invalid.d | 5 +
ld/testsuite/ld-ctf/diag-cttname-invalid.s | 44 +
ld/testsuite/ld-ctf/diag-cttname-null.d | 24 +
ld/testsuite/ld-ctf/diag-cttname-null.s | 44 +
ld/testsuite/ld-ctf/diag-cuname.d | 39 +
ld/testsuite/ld-ctf/diag-cuname.s | 44 +
.../ld-ctf/diag-decompression-failure.d | 5 +
.../ld-ctf/diag-decompression-failure.s | 44 +
ld/testsuite/ld-ctf/diag-parlabel.d | 39 +
ld/testsuite/ld-ctf/diag-parlabel.s | 44 +
ld/testsuite/ld-ctf/diag-parname.d | 5 +
ld/testsuite/ld-ctf/diag-parname.s | 44 +
ld/testsuite/ld-ctf/diag-unsupported-flag.d | 5 +
ld/testsuite/ld-ctf/diag-unsupported-flag.s | 44 +
.../ld-ctf/diag-wrong-magic-number-mixed.d | 39 +
ld/testsuite/ld-ctf/diag-wrong-magic-number.d | 5 +
ld/testsuite/ld-ctf/diag-wrong-magic-number.s | 44 +
ld/testsuite/ld-ctf/enum-2.c | 3 +
ld/testsuite/ld-ctf/enum.c | 3 +
ld/testsuite/ld-ctf/function.c | 3 +
ld/testsuite/ld-ctf/function.d | 23 +
ld/testsuite/ld-ctf/slice.c | 6 +
ld/testsuite/ld-ctf/slice.d | 30 +
ld/testsuite/ld-ctf/super-sub-cycles.c | 10 +
ld/testsuite/ld-ctf/super-sub-cycles.d | 34 +
ld/testsuite/ld-ctf/typedef-int.c | 3 +
ld/testsuite/ld-ctf/typedef-long.c | 3 +
ld/testsuite/ld-ctf/union-1.c | 4 +
ld/testsuite/lib/ld-lib.exp | 52 +
libctf/.gitignore | 1 +
libctf/Makefile.am | 12 +-
libctf/Makefile.in | 360 +-
libctf/aclocal.m4 | 1 +
libctf/config.h.in | 7 +
libctf/configure | 73 +-
libctf/configure.ac | 8 +-
libctf/ctf-archive.c | 147 +-
libctf/ctf-create.c | 112 +-
libctf/ctf-decl.c | 5 +-
libctf/ctf-decls.h | 2 +-
libctf/ctf-dedup.c | 3157 +++++++++++++++++
libctf/ctf-dump.c | 199 +-
libctf/ctf-error.c | 102 +-
libctf/ctf-hash.c | 560 ++-
libctf/ctf-impl.h | 305 +-
libctf/ctf-inlines.h | 97 +
libctf/ctf-link.c | 1191 ++++++-
libctf/ctf-lookup.c | 19 +-
libctf/ctf-open-bfd.c | 85 +-
libctf/ctf-open.c | 91 +-
libctf/ctf-sha1.c | 50 +
libctf/ctf-sha1.h | 41 +
libctf/ctf-subr.c | 101 +-
libctf/ctf-types.c | 508 ++-
libctf/ctf-util.c | 66 +
libctf/libctf.ver | 18 +-
libctf/mkerrors.sed | 28 +
117 files changed, 8997 insertions(+), 619 deletions(-)
create mode 100644 ld/testsuite/ld-ctf/A-2.c
create mode 100644 ld/testsuite/ld-ctf/A.c
create mode 100644 ld/testsuite/ld-ctf/B-2.c
create mode 100644 ld/testsuite/ld-ctf/B.c
create mode 100644 ld/testsuite/ld-ctf/C-2.c
create mode 100644 ld/testsuite/ld-ctf/C.c
create mode 100644 ld/testsuite/ld-ctf/array-char.c
create mode 100644 ld/testsuite/ld-ctf/array-int.c
create mode 100644 ld/testsuite/ld-ctf/array.d
create mode 100644 ld/testsuite/ld-ctf/child-float.c
create mode 100644 ld/testsuite/ld-ctf/child-int.c
create mode 100644 ld/testsuite/ld-ctf/conflicting-cycle-1.B-1.d
create mode 100644 ld/testsuite/ld-ctf/conflicting-cycle-1.B-2.d
create mode 100644 ld/testsuite/ld-ctf/conflicting-cycle-1.parent.d
create mode 100644 ld/testsuite/ld-ctf/conflicting-cycle-2.A-1.d
create mode 100644 ld/testsuite/ld-ctf/conflicting-cycle-2.A-2.d
create mode 100644 ld/testsuite/ld-ctf/conflicting-cycle-2.parent.d
create mode 100644 ld/testsuite/ld-ctf/conflicting-cycle-3.C-1.d
create mode 100644 ld/testsuite/ld-ctf/conflicting-cycle-3.C-2.d
create mode 100644 ld/testsuite/ld-ctf/conflicting-cycle-3.parent.d
create mode 100644 ld/testsuite/ld-ctf/conflicting-enums.d
create mode 100644 ld/testsuite/ld-ctf/conflicting-typedefs.d
create mode 100644 ld/testsuite/ld-ctf/cross-tu-1.c
create mode 100644 ld/testsuite/ld-ctf/cross-tu-2.c
create mode 100644 ld/testsuite/ld-ctf/cross-tu-conflicting-2.c
create mode 100644 ld/testsuite/ld-ctf/cross-tu-cyclic-1.c
create mode 100644 ld/testsuite/ld-ctf/cross-tu-cyclic-2.c
create mode 100644 ld/testsuite/ld-ctf/cross-tu-cyclic-3.c
create mode 100644 ld/testsuite/ld-ctf/cross-tu-cyclic-4.c
create mode 100644 ld/testsuite/ld-ctf/cross-tu-cyclic-conflicting.d
create mode 100644 ld/testsuite/ld-ctf/cross-tu-cyclic-nonconflicting.d
create mode 100644 ld/testsuite/ld-ctf/cross-tu-into-cycle.d
create mode 100644 ld/testsuite/ld-ctf/cross-tu-noncyclic.d
create mode 100644 ld/testsuite/ld-ctf/ctf.exp
create mode 100644 ld/testsuite/ld-ctf/cycle-1.c
create mode 100644 ld/testsuite/ld-ctf/cycle-1.d
create mode 100644 ld/testsuite/ld-ctf/cycle-2.A.d
create mode 100644 ld/testsuite/ld-ctf/cycle-2.B.d
create mode 100644 ld/testsuite/ld-ctf/cycle-2.C.d
create mode 100644 ld/testsuite/ld-ctf/diag-ctf-version-0.d
create mode 100644 ld/testsuite/ld-ctf/diag-ctf-version-0.s
create mode 100644 ld/testsuite/ld-ctf/diag-ctf-version-2-unsupported-feature.d
create mode 100644 ld/testsuite/ld-ctf/diag-ctf-version-2-unsupported-feature.s
create mode 100644 ld/testsuite/ld-ctf/diag-ctf-version-f.d
create mode 100644 ld/testsuite/ld-ctf/diag-ctf-version-f.s
create mode 100644 ld/testsuite/ld-ctf/diag-cttname-invalid.d
create mode 100644 ld/testsuite/ld-ctf/diag-cttname-invalid.s
create mode 100644 ld/testsuite/ld-ctf/diag-cttname-null.d
create mode 100644 ld/testsuite/ld-ctf/diag-cttname-null.s
create mode 100644 ld/testsuite/ld-ctf/diag-cuname.d
create mode 100644 ld/testsuite/ld-ctf/diag-cuname.s
create mode 100644 ld/testsuite/ld-ctf/diag-decompression-failure.d
create mode 100644 ld/testsuite/ld-ctf/diag-decompression-failure.s
create mode 100644 ld/testsuite/ld-ctf/diag-parlabel.d
create mode 100644 ld/testsuite/ld-ctf/diag-parlabel.s
create mode 100644 ld/testsuite/ld-ctf/diag-parname.d
create mode 100644 ld/testsuite/ld-ctf/diag-parname.s
create mode 100644 ld/testsuite/ld-ctf/diag-unsupported-flag.d
create mode 100644 ld/testsuite/ld-ctf/diag-unsupported-flag.s
create mode 100644 ld/testsuite/ld-ctf/diag-wrong-magic-number-mixed.d
create mode 100644 ld/testsuite/ld-ctf/diag-wrong-magic-number.d
create mode 100644 ld/testsuite/ld-ctf/diag-wrong-magic-number.s
create mode 100644 ld/testsuite/ld-ctf/enum-2.c
create mode 100644 ld/testsuite/ld-ctf/enum.c
create mode 100644 ld/testsuite/ld-ctf/function.c
create mode 100644 ld/testsuite/ld-ctf/function.d
create mode 100644 ld/testsuite/ld-ctf/slice.c
create mode 100644 ld/testsuite/ld-ctf/slice.d
create mode 100644 ld/testsuite/ld-ctf/super-sub-cycles.c
create mode 100644 ld/testsuite/ld-ctf/super-sub-cycles.d
create mode 100644 ld/testsuite/ld-ctf/typedef-int.c
create mode 100644 ld/testsuite/ld-ctf/typedef-long.c
create mode 100644 ld/testsuite/ld-ctf/union-1.c
create mode 100644 libctf/.gitignore
create mode 100644 libctf/ctf-dedup.c
create mode 100644 libctf/ctf-inlines.h
create mode 100644 libctf/ctf-sha1.c
create mode 100644 libctf/ctf-sha1.h
create mode 100644 libctf/mkerrors.sed
--
2.27.0.247.g3dff7de930
More information about the Binutils
mailing list