/* Read DWARF package file index sections.

   Copyright (c) 2023 Meta Platforms, Inc. and affiliates.

   This file is part of elfutils.

   This file is free software; you can redistribute it and/or modify

   it under the terms of either

     * the GNU Lesser General Public License as published by the Free

       Software Foundation; either version 3 of the License, or (at

       your option) any later version

   or

     * the GNU General Public License as published by the Free

       Software Foundation; either version 2 of the License, or (at

       your option) any later version

   or both in parallel, as here.

   elfutils is distributed in the hope that it will be useful, but

   WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

   General Public License for more details.

   You should have received copies of the GNU General Public License and

   the GNU Lesser General Public License along with this program.  If

   not, see <http://www.gnu.org/licenses/>.  */

#ifdef HAVE_CONFIG_H

# include <config.h>

#endif

#include <assert.h>

#include "libdwP.h"

static Dwarf_Package_Index *

__libdw_read_package_index (Dwarf *dbg, bool tu)

{

  Elf_Data *data;

  if (tu)

    data = dbg->sectiondata[IDX_debug_tu_index];

  else

    data = dbg->sectiondata[IDX_debug_cu_index];

  /* We need at least 16 bytes for the header.  */

  if (data == NULL || data->d_size < 16)

    {

    invalid:

      __libdw_seterrno (DWARF_E_INVALID_DWARF);

      return NULL;

    }

  const unsigned char *datap = data->d_buf;

  const unsigned char *endp = datap + data->d_size;

  uint16_t version;

  /* In GNU DebugFission for DWARF 4, the version is 2 as a uword.  In the

     standardized DWARF 5 format, it is a uhalf followed by a padding uhalf.

     Check for both.  */

  if (read_4ubyte_unaligned (dbg, datap) == 2)

    version = 2;

  else

    {

      version = read_2ubyte_unaligned (dbg, datap);

      if (version != 5)

  {

    __libdw_seterrno (DWARF_E_VERSION);

    return NULL;

  }

    }

  datap += 4;

  uint32_t section_count = read_4ubyte_unaligned_inc (dbg, datap);

  uint32_t unit_count = read_4ubyte_unaligned_inc (dbg, datap);

  uint32_t slot_count = read_4ubyte_unaligned_inc (dbg, datap);

  /* The specification has a stricter requirement that

     slot_count > 3 * unit_count / 2, but this is enough for us.  */

  if (slot_count < unit_count)

    goto invalid;

  /* After the header, the section must contain:

       8 byte signature per hash table slot

     + 4 byte index per hash table slot

     + Section offset table with 1 header row, 1 row per unit, 1 column per

       section, 4 bytes per field

     + Section size table with 1 row per unit, 1 column per section, 4 bytes

       per field

     We have to be careful about overflow when checking this.  */

  const unsigned char *hash_table = datap;

  if ((size_t) (endp - hash_table) < (uint64_t) slot_count * 12)

    goto invalid;

  const unsigned char *indices = hash_table + (size_t) slot_count * 8;

  const unsigned char *sections = indices + (size_t) slot_count * 4;

  if ((size_t) (endp - sections) < (uint64_t) section_count * 4)

    goto invalid;

  const unsigned char *section_offsets = sections + (size_t) section_count * 4;

  if ((uint64_t) unit_count * section_count > UINT64_MAX / 8

      || ((size_t) (endp - section_offsets)

    < (uint64_t) unit_count * section_count * 8))

    goto invalid;

  const unsigned char *section_sizes

    = section_offsets + (uint64_t) unit_count * section_count * 4;

  Dwarf_Package_Index *index = malloc (sizeof (*index));

  if (index == NULL)

    {

      __libdw_seterrno (DWARF_E_NOMEM);

      return NULL;

    }

  index->dbg = dbg;

  /* Set absent sections to UINT32_MAX.  */

  for (size_t i = 0;

       i < sizeof (index->sections) / sizeof (index->sections[0]); i++)

    index->sections[i] = UINT32_MAX;

  for (size_t i = 0; i < section_count; i++)

    {

      uint32_t section = read_4ubyte_unaligned (dbg, sections + i * 4);

      /* 2 is DW_SECT_TYPES in version 2 and reserved in version 5.  We ignore

         it for version 5.

   5 is DW_SECT_LOC in version 2 and DW_SECT_LOCLISTS in version 5.  We

   use the same index for both.

   7 is DW_SECT_MACINFO in version 2 and DW_SECT_MACRO in version 5.  We

   use the same index for both.

   8 is DW_SECT_MACRO in version 2 and DW_SECT_RNGLISTS in version 5.  We

   use the same index for version 2's DW_SECT_MACRO as version 2's

   DW_SECT_MACINFO/version 5's DW_SECT_MACRO.

   We ignore unknown sections.  */

      if (section == 0)

  continue;

      if (version == 2)

  {

    if (section > 8)

      continue;

    else if (section == 8)

      section = DW_SECT_MACRO;

  }

      else if (section == 2

         || (section

       > sizeof (index->sections) / sizeof (index->sections[0])))

  continue;

      index->sections[section - 1] = i;

    }

  /* DW_SECT_INFO (or DW_SECT_TYPES for DWARF 4 type units) and DW_SECT_ABBREV

     are required.  */

  if (((!tu || dbg->sectiondata[IDX_debug_types] == NULL)

       && index->sections[DW_SECT_INFO - 1] == UINT32_MAX)

      || (tu && dbg->sectiondata[IDX_debug_types] != NULL

    && index->sections[DW_SECT_TYPES - 1] == UINT32_MAX)

      || index->sections[DW_SECT_ABBREV - 1] == UINT32_MAX)

    {

      free (index);

      __libdw_seterrno (DWARF_E_INVALID_DWARF);

      return NULL;

    }

  index->section_count = section_count;

  index->unit_count = unit_count;

  index->slot_count = slot_count;

  index->last_unit_found = 0;

  index->hash_table = hash_table;

  index->indices = indices;

  index->section_offsets = section_offsets;

  index->section_sizes = section_sizes;

  index->debug_info_offsets = NULL;

  return index;

}

static Dwarf_Package_Index *

__libdw_package_index (Dwarf *dbg, bool tu)

{

  if (tu && dbg->tu_index != NULL)

    return dbg->tu_index;

  else if (!tu && dbg->cu_index != NULL)

    return dbg->cu_index;

  Dwarf_Package_Index *index = __libdw_read_package_index (dbg, tu);

  if (index == NULL)

    return NULL;

  /* Offsets in the section offset table are 32-bit unsigned integers.  In

     practice, the .debug_info.dwo section for very large executables can be

     larger than 4GB.  GNU dwp as of binutils 2.41 and llvm-dwp before LLVM 15

     both accidentally truncate offsets larger than 4GB.

     LLVM 15 detects the overflow and errors out instead; see LLVM commit

     f8df8114715b ("[DWP][DWARF] Detect and error on debug info offset

     overflow").  However, lldb in LLVM 16 supports using dwp files with

     truncated offsets by recovering them directly from the unit headers in the

     .debug_info.dwo section; see LLVM commit c0db06227721 ("[DWARFLibrary] Add

     support to re-construct cu-index").  Since LLVM 17, the overflow error can

     be turned into a warning instead; see LLVM commit 53a483cee801 ("[DWP] add

     overflow check for llvm-dwp tools if offset overflow").

     LLVM's support for > 4GB offsets is effectively an extension to the DWARF

     package file format, which we implement here.  The strategy is to walk the

     unit headers in .debug_info.dwo in lockstep with the DW_SECT_INFO columns

     in the section offset tables.  As long as they are in the same order

     (which they are in practice for both GNU dwp and llvm-dwp), we can

     correlate the truncated offset and produce a corrected array of offsets.

     Note that this will be fixed properly in DWARF 6:

     https://dwarfstd.org/issues/220708.2.html.  */

  if (index->sections[DW_SECT_INFO - 1] != UINT32_MAX

      && dbg->sectiondata[IDX_debug_info]->d_size > UINT32_MAX)

    {

      Dwarf_Package_Index *cu_index, *tu_index = NULL;

      if (tu)

  {

    tu_index = index;

    assert (dbg->cu_index == NULL);

    cu_index = __libdw_read_package_index (dbg, false);

    if (cu_index == NULL)

      {

        free(index);

        return NULL;

      }

  }

      else

  {

    cu_index = index;

    if (dbg->sectiondata[IDX_debug_tu_index] != NULL

        && dbg->sectiondata[IDX_debug_types] == NULL)

      {

        assert (dbg->tu_index == NULL);

        tu_index = __libdw_read_package_index (dbg, true);

        if (tu_index == NULL)

    {

      free(index);

      return NULL;

    }

      }

  }

      cu_index->debug_info_offsets = malloc (cu_index->unit_count

               * sizeof (Dwarf_Off));

      if (cu_index->debug_info_offsets == NULL)

  {

    free (tu_index);

    free (cu_index);

    __libdw_seterrno (DWARF_E_NOMEM);

    return NULL;

  }

      if (tu_index != NULL)

  {

    tu_index->debug_info_offsets = malloc (tu_index->unit_count

             * sizeof (Dwarf_Off));

    if (tu_index->debug_info_offsets == NULL)

      {

        free (tu_index);

        free (cu_index->debug_info_offsets);

        free (cu_index);

        __libdw_seterrno (DWARF_E_NOMEM);

        return NULL;

      }

  }

      Dwarf_Off off = 0;

      uint32_t cui = 0, tui = 0;

      uint32_t cu_count = cu_index->unit_count;

      const unsigned char *cu_offset

  = cu_index->section_offsets + cu_index->sections[DW_SECT_INFO - 1] * 4;

      uint32_t tu_count = 0;

      const unsigned char *tu_offset = NULL;

      if (tu_index != NULL)

  {

    tu_count = tu_index->unit_count;

    tu_offset = tu_index->section_offsets

          + tu_index->sections[DW_SECT_INFO - 1] * 4;

  }

      while (cui < cu_count || tui < tu_count)

  {

    Dwarf_Off next_off;

    uint8_t unit_type;

    if (__libdw_next_unit (dbg, false, off, &next_off, NULL, NULL,

         &unit_type, NULL, NULL, NULL, NULL, NULL)

        != 0)

      {

      not_sorted:

        free (cu_index->debug_info_offsets);

        cu_index->debug_info_offsets = NULL;

        if (tu_index != NULL)

    {

      free (tu_index->debug_info_offsets);

      tu_index->debug_info_offsets = NULL;

    }

        break;

      }

    if (unit_type != DW_UT_split_type && cui < cu_count)

      {

        if ((off & UINT32_MAX) != read_4ubyte_unaligned (dbg, cu_offset))

    goto not_sorted;

        cu_index->debug_info_offsets[cui++] = off;

        cu_offset += cu_index->section_count * 4;

      }

    else if (unit_type == DW_UT_split_type && tu_index != NULL

       && tui < tu_count)

      {

        if ((off & UINT32_MAX) != read_4ubyte_unaligned (dbg, tu_offset))

    goto not_sorted;

        tu_index->debug_info_offsets[tui++] = off;

        tu_offset += tu_index->section_count * 4;

      }

    off = next_off;

  }

      if (tu)

  dbg->cu_index = cu_index;

      else if (tu_index != NULL)

  dbg->tu_index = tu_index;

    }

  if (tu)

    dbg->tu_index = index;

  else

    dbg->cu_index = index;

  return index;

}

static int

__libdw_dwp_unit_row (Dwarf_Package_Index *index, uint64_t unit_id,

          uint32_t *unit_rowp)

{

  if (index == NULL)

    return -1;

  uint32_t hash = unit_id;

  uint32_t hash2 = (unit_id >> 32) | 1;

  /* Only check each slot once.  */

  for (uint32_t n = index->slot_count; n-- > 0; )

    {

      size_t slot = hash & (index->slot_count - 1);

      uint64_t sig = read_8ubyte_unaligned (index->dbg,

              index->hash_table + slot * 8);

      if (sig == unit_id)

  {

    uint32_t row = read_4ubyte_unaligned (index->dbg,

            index->indices + slot * 4);

    if (row > index->unit_count)

      {

        __libdw_seterrno (DWARF_E_INVALID_DWARF);

        return -1;

      }

    *unit_rowp = row;

    return 0;

  }

      else if (sig == 0

         && read_4ubyte_unaligned (index->dbg,

           index->indices + slot * 4) == 0)

  break;

      hash += hash2;

    }

  *unit_rowp = 0;

  return 0;

}

static int

__libdw_dwp_section_info (Dwarf_Package_Index *index, uint32_t unit_row,

        unsigned int section, Dwarf_Off *offsetp,

        Dwarf_Off *sizep)

{

  if (index == NULL)

    return -1;

  if (unit_row == 0)

    {

      __libdw_seterrno (DWARF_E_INVALID_DWARF);

      return -1;

    }

  if (index->sections[section - 1] == UINT32_MAX)

    {

      if (offsetp != NULL)

  *offsetp = 0;

      if (sizep != NULL)

  *sizep = 0;

      return 0;

    }

  size_t i = (size_t)(unit_row - 1) * index->section_count

       + index->sections[section - 1];

  if (offsetp != NULL)

    {

      if (section == DW_SECT_INFO && index->debug_info_offsets != NULL)

  *offsetp = index->debug_info_offsets[unit_row - 1];

      else

  *offsetp = read_4ubyte_unaligned (index->dbg,

            index->section_offsets + i * 4);

    }

  if (sizep != NULL)

    *sizep = read_4ubyte_unaligned (index->dbg,

            index->section_sizes + i * 4);

  return 0;

}

int

internal_function

__libdw_dwp_find_unit (Dwarf *dbg, bool debug_types, Dwarf_Off off,

           uint16_t version, uint8_t unit_type, uint64_t unit_id8,

           uint32_t *unit_rowp, Dwarf_Off *abbrev_offsetp)

{

  if (version >= 5

      && unit_type != DW_UT_split_compile && unit_type != DW_UT_split_type)

    {

    not_dwp:

      *unit_rowp = 0;

      *abbrev_offsetp = 0;

      return 0;

    }

  bool tu = unit_type == DW_UT_split_type || debug_types;

  if (dbg->sectiondata[tu ? IDX_debug_tu_index : IDX_debug_cu_index] == NULL)

    goto not_dwp;

  Dwarf_Package_Index *index = __libdw_package_index (dbg, tu);

  if (index == NULL)

    return -1;

  /* This is always called for ascending offsets.  The most obvious way for a

     producer to generate the section offset table is sorted by offset; both

     GNU dwp and llvm-dwp do this.  In this common case, we can avoid the full

     lookup.  */

  if (index->last_unit_found < index->unit_count)

    {

      Dwarf_Off offset, size;

      if (__libdw_dwp_section_info (index, index->last_unit_found + 1,

            debug_types ? DW_SECT_TYPES : DW_SECT_INFO,

            &offset, &size) != 0)

  return -1;

      if (offset <= off && off - offset < size)

  {

    *unit_rowp = ++index->last_unit_found;

    goto done;

  }

      else

  /* The units are not sorted. Don't try again.  */

  index->last_unit_found = index->unit_count;

    }

  if (version >= 5 || debug_types)

    {

      /* In DWARF 5 and in type units, the unit signature is available in the

         unit header.  */

      if (__libdw_dwp_unit_row (index, unit_id8, unit_rowp) != 0)

  return -1;

    }

  else

    {

      /* In DWARF 4 compilation units, the unit signature is an attribute.  We

   can't parse attributes in the split unit until we get the abbreviation

   table offset from the package index, which is a chicken-and-egg

   problem.  We could get the signature from the skeleton unit, but that

   may not be available.

   Instead, we resort to a linear scan through the section offset table.

   Finding all units is therefore quadratic in the number of units.

   However, this will likely never be needed in practice because of the

   sorted fast path above.  If this ceases to be the case, we can try to

   plumb through the skeleton unit's signature when it is available, or

   build a sorted lookup table for binary search.  */

      if (index->sections[DW_SECT_INFO - 1] == UINT32_MAX)

  {

    __libdw_seterrno (DWARF_E_INVALID_DWARF);

    return -1;

  }

      for (uint32_t i = 0; i < index->unit_count; i++)

  {

    Dwarf_Off offset, size;

    __libdw_dwp_section_info (index, i + 1, DW_SECT_INFO, &offset,

            &size);

    if (offset <= off && off - offset < size)

      {

        *unit_rowp = i + 1;

        goto done;

      }

  }

      __libdw_seterrno (DWARF_E_INVALID_DWARF);

      return -1;

    }

 done:

  return __libdw_dwp_section_info (index, *unit_rowp, DW_SECT_ABBREV,

           abbrev_offsetp, NULL);

}

Dwarf_CU *

internal_function

__libdw_dwp_findcu_id (Dwarf *dbg, uint64_t unit_id8)

{

  Dwarf_Package_Index *index = __libdw_package_index (dbg, false);

  uint32_t unit_row;

  Dwarf_Off offset;

  Dwarf_CU *cu;

  if (__libdw_dwp_unit_row (index, unit_id8, &unit_row) == 0

      && __libdw_dwp_section_info (index, unit_row, DW_SECT_INFO, &offset,

           NULL) == 0

      && (cu = __libdw_findcu (dbg, offset, false)) != NULL

      && cu->unit_type == DW_UT_split_compile

      && cu->unit_id8 == unit_id8)

    return cu;

  else

    return NULL;

}

int

dwarf_cu_dwp_section_info (Dwarf_CU *cu, unsigned int section,

         Dwarf_Off *offsetp, Dwarf_Off *sizep)

{

  if (cu == NULL)

    return -1;

  if (section < DW_SECT_INFO || section > DW_SECT_RNGLISTS)

    {

      __libdw_seterrno (DWARF_E_UNKNOWN_SECTION);

      return -1;

    }

  if (cu->dwp_row == 0)

    {

      if (offsetp != NULL)

  *offsetp = 0;

      if (sizep != NULL)

  *sizep = 0;

      return 0;

    }

  else

    {

      Dwarf_Package_Index *index

  = cu->unit_type == DW_UT_split_compile

  ? cu->dbg->cu_index : cu->dbg->tu_index;

      return __libdw_dwp_section_info (index, cu->dwp_row, section, offsetp,

               sizep);

    }

}

INTDEF(dwarf_cu_dwp_section_info)