RFC: DWARF Extensions for Separate Debug Info Files ("Fission")

[Cary Coutant <ccoutant at google dot com>]

At Google, we've found that the cost of linking applications with
debug info is much too high. A large C++ application that might be,
say, 200MB without debug info, is somewhere around 1GB with debug
info, and the total size of the object files that we send to the
linker is around 5GB (and that's with compressed debug sections).
We've come to the conclusion that the most promising solution is to
eliminate the debug info from the link step. I've had direct
experience with HP's approach to this, and I've looked into Sun's and
Apple's approaches, but none of those three approaches actually
separates the debug info from the non-debug info at the object file
(.o) level. I know we're not alone in having concerns about the size
of debug info, so we've developed the following proposal to extend the
DWARF format and produce separate .o and ".dwo" (DWARF object) files
at the compilation step. Our plan is to develop the gcc and gdb
changes on new upstream branches.

After we get the basics working and have some results to show
(assuming it all works out and proves worthwhile), I'll develop this
into a formal proposal to the DWARF committee.

I've also posted this proposal on the GCC wiki:

   http://gcc.gnu.org/wiki/DebugFission

We've named the project "Fission."

I'd appreciate any comments.

-cary


DWARF Extensions for Separate Debug Information Files

September 22, 2011


Problems with Size of the Debug Information
===========================================

Large applications compiled with debug information experience
slow link times, possible out-of-memory conditions at link time,
and slow gdb startup times. In addition, they can contribute to
significant increases in storage requirements, and additional
network latency when transferring files in a distributed build
environment.

* Out-of-memory conditions: When the total size of the input
  files is large, the linker may exceed its total memory
  allocation during the link and may get killed by the operating
  system. As a rule of thumb, the link job total memory
  requirements can be estimated at about 200% of the total size
  of its input files.

* Slow link times: Link times can be frustrating when recompiling
  only a small source file or two. Link times may be aggravated
  when linking on a machine that has insufficient RAM, resulting
  in excessive page thrashing.

* Slow gdb startup times: The debugger today performs a partial
  scan of the debug information in order to build its internal
  tables that allow it to map names and addresses to the debug
  information. This partial scan was designed to improve startup
  performance, and avoids a full scan of the debug information,
  but for large applications, it can still take a minute or more
  before the debugger is ready for the first command. The
  debugger now has the ability to save a ".gdb_index" section in
  the executable and the gold linker now supports a --gdb-index
  option to build this index at link time, but both of these
  options still require the initial partial scan of the debug
  information.

These conditions are largely a direct result of the amount of
debug information generated by the compiler. In a large C++
application compiled with -O2 and -g, the debug information
accounts for 87% of the total size of the object files sent as
inputs to the link step, and 84% of the total size of the output
binary.

Recently, the -Wa,--compress-debug-sections option has been made
available. This option reduces the total size of the object files
sent to the linker by more than a third, so that the debug
information now accounts for 70-80% of the total size of the
object files. The output file is unaffected: the linker
decompresses the debug information in order to link it, and
outputs the uncompressed result (there is an option to recompress
the debug information at link time, but this step would only
reduce the size of the output file without improving link time or
memory usage).


What's All That Space Being Used For?
=====================================

The debugging information in the relocatable object files sent to
the linker consists of a number of separate tables (percentages
are for uncompressed debug information relative to the total
object file size):

* Debug Information Entries - .debug_info (11%): This table
  contains the debug info for subprograms and variables defined
  in the program, and many of the trivial types used.

* Type Units - .debug_types (12%): This table contains the debug
  info for most of the non-trivial types (e.g., structs and
  classes, enums, typedefs), keyed by a hashed type signature so
  that duplicate type definitions can be eliminated by the
  linker. During the link, about 85% of this data is discarded as
  duplicate. These sections have the same structure as the
  .debug_info sections.

* Strings - .debug_str (25%): This table contains strings that
  are not placed inline in the .debug_info and .debug_types
  sections. The linker merges the string tables to eliminate
  duplicates, discarding about 93% of the data as duplicate.

* Range tables - .debug_ranges (2%) and .debug_aranges (0.1%):
  These tables contain range lists to define what pieces of a
  program's text belong to which subprograms and compilation
  units.

* Location lists - .debug_loc (2%): These tables contain lists of
  expressions that describe to the debugger the location of a
  variable based on the PC value.

* Line number tables - .debug_line (1%): These tables contain a
  description of the mapping from PC values to source locations.

* Debug abbreviation codes - .debug_abbrev (<1%): These tables
  provide the definitions for abbreviation codes used in
  describing the debug info in the .debug_info and .debug_types
  sections.

* Public names - .debug_pubnames (<1%): These tables provide a
  list of public names defined in the compilation unit, intended
  to allow the debugger to find the appropriate compilation units
  quickly for a given name. (In practice, these tables are unused
  by gdb.)

* Relocations for debug information (46%): The relocations
  identify to the linker where all the relocatable references are
  in the debug information. Of the 46%, about 20 percentage
  points are for the .debug_info section and about 17 are for the
  .debug_types section. Nine of ten of these relocations are for
  references to the .debug_str section; the remaining tenth are
  mostly references to locations in the program. Another 9
  percentage points are for the .debug_ranges and .debug_loc
  sections; these are entirely references to locations in the
  program. These relocations are used by the linker and are not
  copied to the output file.

Using compressed debug sections, the percentages are adjusted as
follows:

* Debug Information Entries (4%)
* Type Units (7%)
* Strings (10%)
* Range tables (<<1%) (These compress to almost nothing, because
  most of the information is in the relocations.)
* Location lists (1%)
* Line number tables (<1%)
* Debug abbreviation codes (<1%)
* Public names (<1%)
* Relocations (60%) (Relocations are not compressed.)


Towards Reducing the Amount of Debug Information Sent to the Linker
===================================================================

The numbers above suggest several possible approaches to
improving build performance by reducing the amount of debug
information sent to the linker. Of the approaches listed below,
the first has already been implemented, and we are planning to
proceed with options #3 and #5.

1. Compress debug sections

This option is already in the binutils assembler.

Total estimated benefit: 36% reduction

All estimated benefits below assume the use of compressed debug
sections.

2. Intermediate links

We can use intermediate (ld -r) link steps to discard a good
fraction of the duplicate type information and strings in the
debug information. COMDAT elimination on the .debug_types section
would ultimately reduce the total size by 75%, and string merge
processing would ultimately reduce the total size of the
.debug_str section by 80%.

By using ld -r on the input files, there would be some risk of
including object files that would have been passed over during an
archive library search, but this could be mitigated by removing
duplicate definitions of the same symbol in different libraries.

Total estimated benefit: 6% reduction

3. Eliminate relocations to strings

Relocations in the .debug_info and .debug_types sections that
refer to the .debug_str section can be replaced by an extra
indirection and a new dedicated table of string offsets. In the
debug info, each string reference takes 8 bytes in the debug info
plus 24 bytes for the relocation (the 8 bytes compress to 1 byte
on average, but the relocations are not compressed). These would
be replaced by an average 1-2 byte string index, and an 8-byte
string offset in a separate table. The separate table can be
implicitly relocated, so no relocations are necessary, and would
probably compress by about 80% (estimated). Furthermore, the
number of unique strings (within each compilation unit) is only
about 55% of the total number of string references, so the
separate table would be reduced by another 45%.

Total estimated benefit: 53% reduction

4. Move type units to a separate repository

The information in .debug_types is largely independent of the
rest of the compilation unit; each entry describes a type and is
the same in each compilation unit that contains a definition of
that type. The compiler computes a unique signature for each type
definition, and could store the debug info for that type in an
external repository, keyed by the type's signature. This would
reduce the object file size by the 7% used directly for the
.debug_types sections, by another estimated 5% for the strings
referenced by the type entries, and by 22% for the relocations
associated with the .debug_types sections.

Total estimated benefit: 34% reduction (less if option 3 is also
implemented)

5. Move debug info and type units to a ".dwo" file

Alternatively, we can move the .debug_info, .debug_types, and
.debug_str sections from the object (.o) files to a separate
DWARF object (.dwo) file (or ".dsym", in Apple's nomenclature).
Assuming that we could ignore these .dwo files during the link
step, this would remove the bulk of the data that would be sent
to the linker, and debug builds would be be much closer to
non-debug builds in terms of object file size and link speed.

There are two options for how to deal with the separate .dwo
files when it's time to debug a program.

The first option is for the debugger to look for the debug info
directly in the .dwo files, requiring both that the output binary
contains enough information to find the .dwo files, and that the
.dwo files must remain available for use for as long as the
binary might need debugging. This option requires no additional
link step for the debug information.

The second option is to invoke a separate link step to combine
the .dwo files into a single .dwo file that can be easily stored
and located by the debugger (this is the approach that Apple
takes with its dsymutil tool). While this option dramatically
reduces the size of the main link, the separate link step for the
debug information is still close to the original order of
magnitude (debug info being more than 80% of the total size of
the object files). A dsymutil-like linker, however, could be made
to operate much more efficiently than a full-featured ELF linker.

Total estimated benefit: 70% reduction


Previous Implementations of Separate Debug Information
======================================================

Sun, HP, and Apple have all implemented similar mechanisms where
the debug information is not linked into the final binary. All
three implementations simply leave the debug information in the
relocatable object (.o) files, with summary information in the
final binary to enable the debugger to locate the object files
and to apply the relocations to the debug information. Sun's
implementation is for stabs only; for DWARF, the linker always
copies the full debug information to the output file. HP's
implementation is for DWARF, and includes summary information
with the names of the original object files, and a link map that
allows the debugger to locate each object file's contribution to
each section in the output file. Apple's solution is similar, but
the summary information is synthesized by the linker in stabs
format, and the DWARF information is linked together in a
separate link step by the dsymutil utility.

In the Sun and HP implementations, the debug information in the
relocatable objects still requires relocation at debug time, and
the debugger must read the summary information from the
executable file in order to map symbols and sections to the
output file when processing and applying the relocations. The
Apple implementation avoids this cost at debug time, but at the
cost of having a separate link step for the debug information.

As we have seen above, a significant factor in the space used by
debug information is the number of relocations, so a solution
that minimizes the number of relocations not only reduces the
total size of the binary plus its debug information, but also
reduces the complexity and cost of reading the debug information
at debug time.


Design for Moving Debug Information to ".dwo" Files
===================================================

In order for the debugger to be able to locate and process the
information in raw (unrelocated) .dwo files, some information
must still be left behind in the .o files for the linker to
combine and relocate. The bulk of the reduction in .o file size
will come from moving .debug_info, .debug_types, and .debug_str
sections into the .dwo file (and eliminating most of the
associated relocations). Therefore, to simplify the initial
implementation, the .debug_ranges, .debug_loc, .debug_line,
.debug_pubnames, .debug_aranges, and .debug_gdb_scripts sections
(and their relocation sections) will remain in the .o file. The
.debug_abbrev section, although tiny, will naturally move with
the .debug_info and .debug_types sections.

The .dwo file will follow the ELF format, but will have only a
file header, section table, and the debug sections. The debug
sections in the .dwo file will all be named with ".dwo" instead
of ".debug".

For the sections that will move into a .dwo file, the existing
relocations can be handled as follows:

* Each compilation unit header in .debug_info and .debug_types
  normally has a relocation to the corresponding abbrev table.
  This relocation is no longer necessary, and the field in the
  compilation unit header should be interpreted as a direct
  offset relative to the .dwo_abbrev section in the .dwo file.

* The DW_TAG_compile_unit DIE at the top level of the .debug_info
  section contains a relocated reference to a line table in the
  .debug_line section (for the DW_AT_stmt_list attribute). To
  handle this case, the .o file will contain a skeleton
  .debug_info section (and a small associated .debug_abbrev
  section), with a single DW_TAG_compile_unit DIE. The
  DW_TAG_compile_unit DIE will contain the DW_AT_stmt_list
  attribute, and will have no children. The bulk of the debug
  information will instead be placed in the .dwo file in the
  .dwo_info section.

* Likewise, the DW_TAG_type_unit DIE at the top level of the
  .debug_types section normally contains a DW_AT_stmt_list
  attribute with a relocated reference to a line table. In this
  case, the line table serves only to provide a list of directory
  and file names that are indexed by DW_AT_file attributes. For
  this purpose, the .dwo file will contain a skeleton .dwo_line
  section whose only purpose is to list the directories and file
  names needed by DW_AT_file attributes in the type definition.
  Its format will be the same as the .debug_line section, but
  without the line tables. The value of the DW_AT_stmt_list
  attribute in a .dwo_types section will be the unrelocated
  offset to the skeleton line table.

* References to strings in the .dwo_str section will be replaced
  with an indirect string index (using a new FORM code,
  DW_FORM_str_index), expressed as an unsigned LEB128 number. A
  new section in the .dwo file, .dwo_str_offsets, will contain a
  list of offsets to the strings in the string table, and the
  indirect string index will select one of the offsets in that
  list. The entries in .dwo_str_offsets will not need
  relocations.

* References to ranges in the .debug_ranges section, and to
  location lists in the .debug_loc section, from DWARF attributes
  using the form DW_FORM_sec_offset, will be replaced with an
  indirect symbol index (using a new FORM code,
  DW_FORM_ref_index), expressed as an unsigned LEB128 number. A
  new section in the .o file, .debug_ref, will contain a list of
  relocated addresses, one for each reference needed. Each entry
  in the .debug_ref section will be a 4- or 8-byte location
  (depending on the format of the DWARF information), with the
  relocation that applied to the original reference. The linker
  will combine the .debug_ref sections from all the input .o
  files, and will apply the relocations normally. In order for
  the debugger to find the contribution to the .debug_ref section
  corresponding to a particular compilation unit, the skeleton
  DW_TAG_compile_unit entry in the .o file's .debug_info section
  will contain a DW_AT_dwo_name attribute to identify the .dwo
  file, and a DW_AT_ref_base attribute whose value points to the
  base of that compilation unit's .debug_ref contribution.

* Similarly, references to addresses in loadable sections (e.g.,
  .text or .data), from DWARF attributes using the form
  DW_FORM_addr, will be replaced with an indirect symbol index
  (using a new FORM code, DW_FORM_addr_index), expressed as an
  unsigned LEB128 number. A new section in the .o file,
  .debug_addr, will contain a list of relocated addresses, one
  for each reference needed. Each entry in the .debug_addr
  section will be an address-sized value, with the relocation
  that applied to the original reference. The linker will combine
  the .debug_addr sections from all the input .o files, and will
  apply the relocations normally. In order for the debugger to
  find the contribution to the .debug_ref section corresponding
  to a particular compilation unit, the skeleton
  DW_TAG_compile_unit entry in the .o file's .debug_info section
  will also contain a DW_AT_addr_base attribute whose value
  points to the base of that compilation unit's .debug_addr
  contribution.

In the initial implementation, we will modify gcc to emit all the
debug information into the single .o file, and we will use
post-compile processing to move the appropriate sections into the
separate .dwo file.

The debug sections to remain in the .o file are:

* .debug_abbrev - Defines the abbreviation codes used by the
  skeleton .debug_info section.

* .debug_info - Contains the skeleton DW_TAG_compile_unit DIE.
  This DIE has the following attributes: DW_AT_comp_dir,
  DW_AT_dwo_name, DW_AT_dwo_id, DW_AT_ref_base, and
  DW_AT_addr_base. (All string attributes will use
  DW_FORM_string, so no .debug_str section is necessary in the .o
  file.)

* .debug_ref - New section to hold references to other debug
  sections, indexed by attributes of DW_FORM_ref_index.

* .debug_addr - New section to hold references to loadable
  sections, indexed by attributes of form DW_FORM_addr_index.

* .debug_line - Line tables, unaffected by this design. (These
  could be moved to the .dwo file, but in order to do so, each
  DW_LNE_set_address opcode would need to be replaced by a new
  opcode that referenced an entry in the .debug_addr section.)

* .debug_loc - Location lists, unaffected by this design.

* .debug_ranges - Range lists, unaffected by this design.

* .debug_macinfo - Macro information, unaffected by this design.

* .debug_pubnames - Public names for use in building the
  .gdb_index section at link time. This section will have the
  same format and use as always, but we will fix gcc to emit all
  names that need to appear in the index.

* .debug_pubtypes - Public types for use in building the
  .gdb_index section at link time. This section will have an
  extended format to allow it to represent both types in the
  .debug_dwo_info section and type units in .debug_types.

* .debug_aranges - Range table for the compilation unit, for use
  in building the .gdb_index section at link time. It's likely,
  but unverified, that the contents of this section as produced
  by gcc today are sufficient for this use.

The following debug sections will be generated by gcc and the
assembler in the .o file, but will be moved to the separate .dwo
file in post-compile processing:

* .dwo_abbrev - Defines the abbreviation codes used by the
  .debug_dwo_info section.

* .dwo_info - Contains the complete debug information for the
  compilation unit. The top-level DW_TAG_compile_unit DIE will
  contain the standard attributes (with the possible addition of
  DW_AT_id to match the .dwo file with the corresponding .o
  file).

* .dwo_types - Contains the complete debug information for each
  type unit. (There may be multiple instances of this section.
  Unlike in a .o file, the .dwo_types sections will not be placed
  in COMDAT groups.)

* .dwo_str - Contains the strings referenced indirectly via
  DW_FORM_strp from the .dwo_info and .dwo_types sections.

* .dwo_str_offsets - Contains an array of offsets of strings in
  the .dwo_str section. Attributes using DW_FORM_str_index will
  reference an entry in this array.


Building a GDB Index
====================

In order to build the .gdb_index section, the linker today needs
to do three things:

1.  Scan the .debug_info sections to extract all the public names
    mentioned in those sections and build a hash table mapping
    those names to a list of compilation units that provide
    definitions for those names.

2.  Scan the compilation unit headers of the .debug_info sections
    to build a list of compilation units, and to build a range
    table that can be used to map and address to a specific
    compilation unit.

3.  Scan the .debug_types sections to build a list of type units.

In this new design, the .debug_info and .debug_types sections
will not be available for the linker to scan. Instead, the linker
will extract the public names from the .debug_pubnames and
.debug_pubtypes sections, the range table from the .debug_aranges
sections, and the the list of type units from the .debug_pubtypes
sections.

The format of the .gdb_index section will remain unchanged (with
the possible exception of removing the range tables in favor of
having gdb use .debug_aranges directly).

The .debug_pubnames section was always intended as a
comprehensive list of symbols that gdb could use for quick
lookup, but bugs in gcc have so far prevented gdb from using this
section for its intended purpose, and the .gdb_index section has
instead been built from a scan over the .debug_info section. We
will need to fix gcc so that the .debug_pubnames section contains
all of the names that gdb requires in its index.

The .debug_pubtypes section, likewise, was intended as a list of
public types, but has not yet been extended to include type
defined in type units in the .debug_types sections. We will have
to extend the format to allow this, and modify gcc to produce the
required information.

The .debug_aranges section currently contains all the required
information for producing the .gdb_index section (as far as I
know), and could in fact be used directly by gdb instead of
having the linker reformat its contents into .gdb_index. We can
either modify the linker to extract the necessary range
information from .debug_aranges to produce .gdb_index, or modify
gdb to use the existing information from .debug_aranges instead
of expecting it in .gdb_index.


Proposed Extensions to the DWARF Specification
==============================================

We propose adding several new sections, attribute codes, and form
codes to the DWARF specification, and extending the
.debug_pubtypes format to support type units.

New DWARF sections

* .debug_ref -- This section contains relocated references to the
  .debug_ranges and .debug_loc sections. No header is required;
  the base of each compilation unit's contribution to the section
  is given by the DW_AT_ref_base attribute of the
  DW_TAG_compile_unit DIE in the .debug_info section. Each entry
  is 4 bytes for DWARF-32 compilation units, or 8 bytes for
  DWARF-64 compilation units, as determined by the unit_length
  field of the compilation unit header in the .debug_info
  section.

* .debug_addr -- This section contains relocated references to
  loadable sections in the program. No header is required; the
  base of each compilation unit's contribution to the section is
  given by the DW_AT_addr_base attribute of the
  DW_TAG_compile_unit DIE in the .debug_info section. Each entry
  is 4 or 8 bytes, depending on the address_size field of the
  compilation unit header in the .debug_info section.

* .dwo_abbrev -- This section contains the abbreviation table for
  the .dwo_info section. Its format is identical to the
  .debug_abbrev section.

* .dwo_info -- This section contains the bulk of the debug
  information for a compilation unit. Its format is identical to
  the .debug_info section. The DW_AT_dwo_name attribute of the
  DW_TAG_compile_unit DIE in the .debug_info section is used to
  locate the .dwo file, and the DW_AT_dwo_id attribute of the
  DW_TAG_compile_unit DIE in each section use used to verify a
  match.

* .dwo_types -- This section contains a type unit. Its format is
  identical to the .debug_types section. Each type unit is placed
  in a separate .dwo_types section; unlike .debug_types sections,
  however, .dwo_types sections are not placed in COMDAT groups.

* .dwo_str -- This section contains the DWARF string table. Its
  format is identical to the .debug_str section.

* .dwo_str_offsets -- This section contains a list of offsets to
  strings in the .dwo_str section. References to strings using
  the DW_FORM_str_index form code refer to an entry in this
  section. No header is required. The size of each entry is 4
  bytes for DWARF-32 compilation units, or 8 bytes for DWARF-64
  compilation units, as determined by the unit_length field of
  the compilation unit header in the .dwo_info section. Entries
  in this section are not relocated--each entry is an offset
  relative to the beginning of the .dwo_str section in the same
  .dwo file.

New DWARF attributes

* DW_AT_dwo_name -- A string-valued attribute that identifies the
  name of the corresponding .dwo file. This attribute is found in
  the DW_TAG_compile_unit DIE of the .debug_info section.

* DW_AT_dwo_id -- A block-valued attribute that provides a unique
  ID for the compilation unit. This attribute is found in the
  DW_TAG_compile_unit DIE in both .debug_info and .dwo_info
  sections, and can be used to verify a match between .o file (or
  linked binary) and .dwo file.

* DW_AT_ref_base -- A reference-valued attribute that refers to
  the beginning of the compilation unit's contribution to the
  .debug_ref section. This attribute is found in the
  DW_TAG_compile_unit DIE of the .debug_info section.

* DW_AT_addr_base -- A reference-valued attribute that refers to
  the beginning of the compilation unit's contribution to the
  .debug_addr section. This attribute is found in the
  DW_TAG_compile_unit DIE of the .debug_info section.

New DWARF form codes

* DW_FORM_ref_index -- An unsigned LEB128 value that refers to an
  entry in the .debug_ref section. This form belongs to the
  reference class, and may be used in a .dwo_info section for any
  attribute that would have otherwise used another
  reference-class form to refer to an entry in the .debug_ranges
  or .debug_loc section. The first entry in the compilation
  unit's contribution to the debug_ref section has an index of 0.

* DW_FORM_addr_index -- An unsigned LEB128 value that refers to
  an entry in the .debug_addr section. This form belongs to the
  address class, and may be used in a .dwo_info section for any
  attribute that would have otherwise used DW_FORM_addr to refer
  to an address in a loadable section of the linked binary. The
  first entry in the compilation unit's contribution to the
  debug_addr section has an index of 0.

* DW_FORM_str_index -- An unsigned LEB128 value that refers to an
  entry in the .dwo_str_offsets section. This form belongs to the
  string class, and may be used in a .dwo_info or .dwo_types
  section for any attribute that would have otherwise used
  DW_FORM_strp to refer to a string in the .debug_str section.
  The first entry in the .dwo_str_offsets section has an index of
  0.

Extension to .debug_pubtypes

The .debug_pubtypes table will be extended with a second table of
type units following the existing table of name entries. Each
entry in the table of type units will consist of two fields: an
eight-byte type signature, followed by the null-terminated name
of the type. The final entry of the table will be followed by an
entry where the signature is all zeroes, and the name is a single
null byte. The version number in the .debug_pubtypes header will
change to 5 to mark the presence of this second table.