Fix 100x slowdown regression on DWZ files

Fix 100x slowdown regression on DWZ files

Since Fedora started to use DWZ DWARF compressor:
	http://fedoraproject.org/wiki/Features/DwarfCompressor
GDB has slowed down a lot.  To make it clear - DWZ is DWARF structure
rearrangement, "compressor" does not mean any zlib style data compression.

This patch reduces LibreOffice backtrace from 5 minutes to 3 seconds (100x)
and it also reduces memory consumption 20x.
[ benchmark is at the bottom of this mail ]

Example of DWZ output:
------------------------------------------------------------------------------
  Compilation Unit @ offset 0xc4:
 <0><cf>: Abbrev Number: 17 (DW_TAG_partial_unit)
    <d0>   DW_AT_stmt_list   : 0x0
    <d4>   DW_AT_comp_dir    : (indirect string, offset: 0x6f): /usr/src/debug/gdb-7.7.1/build-x86_64-redhat-linux-gnu/gdb
 <1><d8>: Abbrev Number: 9 (DW_TAG_typedef)
    <d9>   DW_AT_name        : (indirect string, offset: 0x827dc): size_t
    <dd>   DW_AT_decl_file   : 4
    <de>   DW_AT_decl_line   : 212
    <df>   DW_AT_type        : <0xae>

  Compilation Unit @ offset 0xe4:
 <0><ef>: Abbrev Number: 13 (DW_TAG_partial_unit)
    <f0>   DW_AT_stmt_list   : 0x0
    <f4>   DW_AT_comp_dir    : (indirect string, offset: 0x6f): /usr/src/debug/gdb-7.7.1/build-x86_64-redhat-linux-gnu/gdb
 <1><f8>: Abbrev Number: 45 (DW_TAG_typedef)
    <f9>   DW_AT_name        : (indirect string, offset: 0x251): __off_t
    <fd>   DW_AT_decl_file   : 3
    <fe>   DW_AT_decl_line   : 131
    <ff>   DW_AT_type        : <0x68>

  Compilation Unit @ offset 0x62d9f9:
 <0><62da04>: Abbrev Number: 20 (DW_TAG_compile_unit)
[...]
    <62da12>   DW_AT_low_pc	 : 0x807e10
    <62da1a>   DW_AT_high_pc     : 134
    <62da1c>   DW_AT_stmt_list   : 0xf557e
 <1><62da20>: Abbrev Number: 7 (DW_TAG_imported_unit)
    <62da21>   DW_AT_import	 : <0xcf>	[Abbrev Number: 17]
------------------------------------------------------------------------------

One can see all DW_TAG_partial_unit have DW_AT_stmt_list 0x0 which causes
repeated decoding of that .debug_line unit on each DW_TAG_imported_unit.

This was OK before as each DW_TAG_compile_unit has its own .debug_line unit.
But since the introduction of DW_TAG_partial_unit by DWZ one should cache
read-in DW_AT_stmt_list .debug_line units.

Fortunately one does not need to cache whole
        struct linetable *symtab->linetable
and other data from .debug_line mapping PC<->lines
------------------------------------------------------------------------------
 Line Number Statements:
  Extended opcode 2: set Address to 0x45c880
  Advance Line by 25 to 26
  Copy
------------------------------------------------------------------------------
as the only part of .debug_line which GDB needs for DW_TAG_partial_unit is:
------------------------------------------------------------------------------
 The Directory Table:
  ../../gdb
  /usr/include/bits
[...]
 The File Name Table:
  Entry Dir     Time    Size    Name
  1     1	0	0	gdb.c
  2     2	0	0	string3.h
[...]
------------------------------------------------------------------------------
specifically referenced in GDB for DW_AT_decl_file at a single place:
------------------------------------------------------------------------------
              fe = &cu->line_header->file_names[file_index - 1];
              SYMBOL_SYMTAB (sym) = fe->symtab;
------------------------------------------------------------------------------

This is because for some reason DW_TAG_partial_unit never contains PC-related
DWARF information.  I do not know exactly why, the compression ratio is a bit
lower due to it but thanksfully currently it is that way:
dwz.c:
------------------------------------------------------------------------------
        /* These attributes reference code, prevent moving
           DIEs with them.  */
        case DW_AT_low_pc:
        case DW_AT_high_pc:
        case DW_AT_entry_pc:
        case DW_AT_ranges:
          die->die_ck_state = CK_BAD;
+
  /* State of checksum computation.  Not computed yet, computed and
     suitable for moving into partial units, currently being computed
     and finally determined unsuitable for moving into partial units.  */
  enum { CK_UNKNOWN, CK_KNOWN, CK_BEING_COMPUTED, CK_BAD } die_ck_state : 2;
------------------------------------------------------------------------------
I have also verified also real-world Fedora debuginfo files really comply with
that assumption with dwgrep
	https://github.com/pmachata/dwgrep
using:
------------------------------------------------------------------------------
dwgrep -e 'entry ?DW_TAG_partial_unit child* ( ?DW_AT_low_pc , ?DW_AT_high_pc , ?DW_AT_ranges )' /usr/lib/debug/**
------------------------------------------------------------------------------

BTW I think GDB already does not support the whole DW_TAG_imported_unit and
DW_TAG_partial_unit usage possibilities as specified by the DWARF standard.
I think GDB would not work if DW_TAG_imported_unit was used in some inner
level and not at the CU level (readelf -wi level <1>) - this is how DWZ is
using DW_TAG_imported_unit.  Therefore I do not think further assumptions
about DW_TAG_imported_unit and DW_TAG_partial_unit usage by DWZ are a problem
for GDB.

One could save the whole .debug_line decoded PC<->lines mapping (and not just
the DW_AT_decl_file table) but:
 * there are some problematic corner cases so one could do it incorrectly
 * there are no real world data to really test such patch extension
 * such extension could be done perfectly incrementally on top of this patch

------------------------------------------------------------------------------

benchmark - on Fedora 20 x86_64 and FSF GDB HEAD:
echo -e 'thread apply all bt\nset confirm no\nq'|./gdb -p `pidof soffice.bin` -ex 'set pagination off' -ex 'maintenance set per-command
space' -ex 'maintenance set per-command symtab' -ex 'maintenance set per-command time'

FSF GDB HEAD ("thread apply all bt"):
Command execution time: 333.693000 (cpu), 335.587539 (wall)
                                          ---sec
Space used: 1736404992 (+1477189632 for this command)
                         ----MB
vs.
THIS PATCH ("thread apply all bt"):
Command execution time: 2.595000 (cpu), 2.607573 (wall)
                                        -sec
Space used: 340058112 (+85917696 for this command)
                        --MB

FSF GDB HEAD ("thread apply all bt full"):
Command execution time: 466.751000 (cpu), 468.345837 (wall)
                                          ---sec
Space used: 2330132480 (+2070974464 for this command)
                         ----MB
vs.
THIS PATCH ("thread apply all bt full"):
Command execution time: 18.907000 (cpu), 18.964125 (wall)
                                         --sec
Space used: 364462080 (+110325760 for this command)
                        ---MB

------------------------------------------------------------------------------

gdb/ChangeLog
2015-01-24  Jan Kratochvil  <jan.kratochvil@redhat.com>

	Fix 100x slowdown regression on DWZ files.
	* dwarf2read.c (struct dwarf2_per_objfile): Add line_header_hash.
	(struct line_header): Add offset and offset_in_dwz.
	(dwarf_decode_lines): Add parameter decode_mapping to the declaration.
	(free_line_header_voidp): New declaration.
	(line_header_hash, line_header_hash_voidp, line_header_eq_voidp): New
	functions.
	(dwarf2_build_include_psymtabs): Update dwarf_decode_lines caller.
	(handle_DW_AT_stmt_list): Use line_header_hash.
	(free_line_header_voidp): New function.
	(dwarf_decode_line_header): Initialize offset and offset_in_dwz.
	(dwarf_decode_lines): New parameter decode_mapping, use it.
	(dwarf2_free_objfile): Free line_header_hash.