// Copyright 2018 The Abseil Authors.

//

// Licensed under the Apache License, Version 2.0 (the "License");

// you may not use this file except in compliance with the License.

// You may obtain a copy of the License at

//

//      https://www.apache.org/licenses/LICENSE-2.0

//

// Unless required by applicable law or agreed to in writing, software

// distributed under the License is distributed on an "AS IS" BASIS,

// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

// See the License for the specific language governing permissions and

// limitations under the License.

// This library provides Symbolize() function that symbolizes program

// counters to their corresponding symbol names on linux platforms.

// This library has a minimal implementation of an ELF symbol table

// reader (i.e. it doesn't depend on libelf, etc.).

//

// The algorithm used in Symbolize() is as follows.

//

//   1. Go through a list of maps in /proc/self/maps and find the map

//   containing the program counter.

//

//   2. Open the mapped file and find a regular symbol table inside.

//   Iterate over symbols in the symbol table and look for the symbol

//   containing the program counter.  If such a symbol is found,

//   obtain the symbol name, and demangle the symbol if possible.

//   If the symbol isn't found in the regular symbol table (binary is

//   stripped), try the same thing with a dynamic symbol table.

//

// Note that Symbolize() is originally implemented to be used in

// signal handlers, hence it doesn't use malloc() and other unsafe

// operations.  It should be both thread-safe and async-signal-safe.

//

// Implementation note:

//

// We don't use heaps but only use stacks.  We want to reduce the

// stack consumption so that the symbolizer can run on small stacks.

//

// Here are some numbers collected with GCC 4.1.0 on x86:

// - sizeof(Elf32_Sym)  = 16

// - sizeof(Elf32_Shdr) = 40

// - sizeof(Elf64_Sym)  = 24

// - sizeof(Elf64_Shdr) = 64

//

// This implementation is intended to be async-signal-safe but uses some

// functions which are not guaranteed to be so, such as memchr() and

// memmove().  We assume they are async-signal-safe.

#include <dlfcn.h>

#include <elf.h>

#include <fcntl.h>

#include <link.h>  // For ElfW() macro.

#include <sys/resource.h>

#include <sys/stat.h>

#include <sys/types.h>

#include <unistd.h>

#include <algorithm>

#include <array>

#include <atomic>

#include <cerrno>

#include <cinttypes>

#include <climits>

#include <cstdint>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iterator>

#include <memory>

#include "absl/base/casts.h"

#include "absl/base/dynamic_annotations.h"

#include "absl/base/internal/low_level_alloc.h"

#include "absl/base/internal/raw_logging.h"

#include "absl/base/internal/spinlock.h"

#include "absl/base/port.h"

#include "absl/debugging/internal/demangle.h"

#include "absl/debugging/internal/vdso_support.h"

#include "absl/strings/string_view.h"

namespace absl {

ABSL_NAMESPACE_BEGIN

// Value of argv[0]. Used by MaybeInitializeObjFile().

static char *argv0_value = nullptr;

void InitializeSymbolizer(const char *argv0) {

#ifdef ABSL_HAVE_VDSO_SUPPORT

  // We need to make sure VDSOSupport::Init() is called before any setuid or

  // chroot calls, so InitializeSymbolizer() should be called very early in the

  // life of a program.

  absl::debugging_internal::VDSOSupport::Init();

#endif

  if (argv0_value != nullptr) {

    free(argv0_value);

    argv0_value = nullptr;

  }

  if (argv0 != nullptr && argv0[0] != '\0') {

    argv0_value = strdup(argv0);

  }

}

namespace debugging_internal {

namespace {

// Re-runs fn until it doesn't cause EINTR.

#define NO_INTR(fn) \

  do {              \

  } while ((fn) < 0 && errno == EINTR)

// On Linux, ELF_ST_* are defined in <linux/elf.h>.  To make this portable

// we define our own ELF_ST_BIND and ELF_ST_TYPE if not available.

#ifndef ELF_ST_BIND

#define ELF_ST_BIND(info) (((unsigned char)(info)) >> 4)

#endif

#ifndef ELF_ST_TYPE

#define ELF_ST_TYPE(info) (((unsigned char)(info)) & 0xF)

#endif

// Some platforms use a special .opd section to store function pointers.

const char kOpdSectionName[] = ".opd";

#if defined(__powerpc64__) && defined(_CALL_ELF)

#if _CALL_ELF <= 1

#define ABSL_INTERNAL_HAVE_PPC64_ELFV1_ABI 1

#endif

#endif

#if defined(ABSL_INTERNAL_HAVE_PPC64_ELFV1_ABI) || defined(__ia64)

// Use opd section for function descriptors on these platforms, the function

// address is the first word of the descriptor.

//

// https://maskray.me/blog/2023-02-26-linker-notes-on-power-isa notes that

// opd sections are used on 64-bit PowerPC with the ELFv1 ABI.

inline constexpr bool kPlatformUsesOPDSections = true;

#else

inline constexpr bool kPlatformUsesOPDSections = false;

#endif

// This works for PowerPC & IA64 only.  A function descriptor consist of two

// pointers and the first one is the function's entry.

const size_t kFunctionDescriptorSize = sizeof(void *) * 2;

std::atomic<SymbolDecorator::Factory*> g_decorator_factory = nullptr;

struct FileMappingHint {

  const void *start;

  const void *end;

  uint64_t offset;

  const char *filename;

};

const int kMaxFileMappingHints = 8;

int g_num_file_mapping_hints;

FileMappingHint g_file_mapping_hints[kMaxFileMappingHints];

// Protects g_file_mapping_hints.

ABSL_CONST_INIT absl::base_internal::SpinLock g_file_mapping_mu(

    absl::base_internal::SCHEDULE_KERNEL_ONLY);

// Async-signal-safe function to zero a buffer.

// memset() is not guaranteed to be async-signal-safe.

static void SafeMemZero(void *p, size_t size) {

  unsigned char *c = static_cast<unsigned char *>(p);

  while (size--) {

    *c++ = 0;

  }

}

struct ObjFile {

  char *filename = nullptr;

  const void *start_addr = nullptr;

  const void *end_addr = nullptr;

  uint64_t offset = 0;

  // The following fields are initialized on the first access to the

  // object file.

  int fd = -1;

  int elf_type = -1;

  ElfW(Ehdr) elf_header = {};

  // PT_LOAD program header describing executable code.

  // Normally we expect just one, but SWIFT binaries have two.

  // CUDA binaries have 3 (see cr/473913254 description).

  std::array<ElfW(Phdr), 4> phdr = {};

  SymbolDecoratorPtr decorator = {};

};

// Build 4-way associative cache for symbols. Within each cache line, symbols

// are replaced in LRU order.

enum {

  ASSOCIATIVITY = 4,

};

struct SymbolCacheLine {

  const void *pc[ASSOCIATIVITY];

  char *name[ASSOCIATIVITY];

  // age[i] is incremented when a line is accessed. it's reset to zero if the

  // i'th entry is read.

  uint32_t age[ASSOCIATIVITY];

};

// ---------------------------------------------------------------

// An AddrMap is a vector of ObjFile, using SigSafeArena() for allocation.

class AddrMap {

 public:

  AddrMap() : size_(0), allocated_(0), obj_(nullptr) {}

  ~AddrMap() { base_internal::LowLevelAlloc::Free(obj_); }

  size_t Size() const { return size_; }

  ObjFile *At(size_t i) { return &obj_[i]; }

  ObjFile *Add();

  void Clear();

 private:

  size_t size_;       // count of valid elements (<= allocated_)

  size_t allocated_;  // count of allocated elements

  ObjFile *obj_;      // array of allocated_ elements

  AddrMap(const AddrMap &) = delete;

  AddrMap &operator=(const AddrMap &) = delete;

};

void AddrMap::Clear() {

  for (size_t i = 0; i != size_; i++) {

    At(i)->~ObjFile();

  }

  size_ = 0;

}

ObjFile *AddrMap::Add() {

  if (size_ == allocated_) {

    size_t new_allocated = allocated_ * 2 + 50;

    ObjFile *new_obj_ =

        static_cast<ObjFile *>(base_internal::LowLevelAlloc::AllocWithArena(

            new_allocated * sizeof(*new_obj_), base_internal::SigSafeArena()));

    if (obj_) {

      std::uninitialized_move_n(obj_, size_, new_obj_);

      std::destroy_n(obj_, size_);

      base_internal::LowLevelAlloc::Free(obj_);

    }

    obj_ = new_obj_;

    allocated_ = new_allocated;

  }

  return new (&obj_[size_++]) ObjFile;

}

class CachingFile {

 public:

  // Setup reader for fd that uses buf[0, buf_size-1] as a cache.

  CachingFile(int fd, char *buf, size_t buf_size)

      : fd_(fd),

        cache_(buf),

        cache_size_(buf_size),

        cache_start_(0),

        cache_limit_(0) {}

  int fd() const { return fd_; }

  ssize_t ReadFromOffset(void *buf, size_t count, off_t offset);

  bool ReadFromOffsetExact(void *buf, size_t count, off_t offset);

 private:

  // Bytes [cache_start_, cache_limit_-1] from fd_ are stored in

  // a prefix of cache_[0, cache_size_-1].

  int fd_;

  char *cache_;

  size_t cache_size_;

  off_t cache_start_;

  off_t cache_limit_;

};

// ---------------------------------------------------------------

enum FindSymbolResult { SYMBOL_NOT_FOUND = 1, SYMBOL_TRUNCATED, SYMBOL_FOUND };

class Symbolizer {

 public:

  Symbolizer();

  ~Symbolizer();

  const char *GetSymbol(const void *const pc);

  void UpdateDecoratorsIfNeeded(SymbolDecorator::Factory* decorator_factory);

 private:

  char *CopyString(const char *s) {

    size_t len = strlen(s);

    char *dst =

        static_cast<char *>(base_internal::LowLevelAlloc::AllocWithArena(

            len + 1, base_internal::SigSafeArena()));

    ABSL_RAW_CHECK(dst != nullptr, "out of memory");

    memcpy(dst, s, len + 1);

    return dst;

  }

  ABSL_ATTRIBUTE_NOINLINE ObjFile* FindObjFile(const void* const start,

                                               size_t size);

  static bool RegisterObjFile(const char *filename,

                              const void *const start_addr,

                              const void *const end_addr, uint64_t offset,

                              void *arg);

  SymbolCacheLine *GetCacheLine(const void *const pc);

  const char *FindSymbolInCache(const void *const pc);

  const char *InsertSymbolInCache(const void *const pc, const char *name);

  void AgeSymbols(SymbolCacheLine *line);

  void ClearAddrMap();

  FindSymbolResult GetSymbolFromObjectFile(const ObjFile &obj,

                                           const void *const pc,

                                           const ptrdiff_t relocation,

                                           char *out, size_t out_size,

                                           char *tmp_buf, size_t tmp_buf_size);

  const char *GetUncachedSymbol(const void *pc);

  enum {

    SYMBOL_BUF_SIZE = 3072,

    TMP_BUF_SIZE = 1024,

    SYMBOL_CACHE_LINES = 128,

    FILE_CACHE_SIZE = 8192,

  };

  AddrMap addr_map_;

  SymbolDecorator::Factory* decorator_factory_ = nullptr;

  bool ok_;

  bool addr_map_read_;

  char symbol_buf_[SYMBOL_BUF_SIZE];

  char file_cache_[FILE_CACHE_SIZE];

  // tmp_buf_ will be used to store arrays of ElfW(Shdr) and ElfW(Sym)

  // so we ensure that tmp_buf_ is properly aligned to store either.

  alignas(16) char tmp_buf_[TMP_BUF_SIZE];

  static_assert(alignof(ElfW(Shdr)) <= 16,

                "alignment of tmp buf too small for Shdr");

  static_assert(alignof(ElfW(Sym)) <= 16,

                "alignment of tmp buf too small for Sym");

  SymbolCacheLine symbol_cache_[SYMBOL_CACHE_LINES];

};

// Protect against client code closing low-valued file descriptors it doesn't

// actually own.

int OpenReadOnlyWithHighFD(const char *fname) {

  static int high_fd = [] {

    struct rlimit rlim{};

    const int rc = getrlimit(RLIMIT_NOFILE, &rlim);

    if (rc == 0 && rlim.rlim_cur >= 2000) {

      const int max_fd = static_cast<int>(rlim.rlim_cur);

      // This will return 2000 on reasonably-configured systems.

      return std::min<int>(2000, max_fd - 1000);

    }

    ABSL_RAW_LOG(WARNING, "Unable to get high fd: rc=%d, limit=%ld",  //

                 rc, static_cast<long>(rlim.rlim_cur));

    return -1;

  }();

  constexpr int kOpenFlags = O_RDONLY | O_CLOEXEC;

  if (high_fd >= 1000) {

    const int fd = open(fname, kOpenFlags);

    if (fd != -1 && fd < high_fd) {

      // Try to relocate fd to high range.

      static_assert(kOpenFlags & O_CLOEXEC,

                    "F_DUPFD_CLOEXEC assumes O_CLOEXEC");

      const int fd2 = fcntl(fd, F_DUPFD_CLOEXEC, high_fd);

      if (fd2 != -1) {

        // Successfully obtained high fd. Use it.

        close(fd);

        return fd2;

      } else {

        ABSL_RAW_LOG(WARNING, "Unable to dup fd=%d above %d, errno=%d", fd,

                     high_fd, errno);

      }

    }

    // Either open failed and fd==-1, or fd is already above high_fd, or fcntl

    // failed and fd is valid (but low).

    return fd;

  }

  return open(fname, kOpenFlags);

}

static std::atomic<Symbolizer *> g_cached_symbolizer;

}  // namespace

static size_t SymbolizerSize() {

  auto pagesize = static_cast<size_t>(sysconf(_SC_PAGESIZE));

  return ((sizeof(Symbolizer) - 1) / pagesize + 1) * pagesize;

}

// Return (and set null) g_cached_symbolized_state if it is not null.

// Otherwise return a new symbolizer.

static Symbolizer *AllocateSymbolizer() {

  base_internal::InitSigSafeArena();

  Symbolizer *symbolizer =

      g_cached_symbolizer.exchange(nullptr, std::memory_order_acquire);

  if (symbolizer == nullptr) {

    void* ptr = base_internal::LowLevelAlloc::AllocWithArena(

        SymbolizerSize(), base_internal::SigSafeArena());

    symbolizer = new (ptr) Symbolizer();

  }

  symbolizer->UpdateDecoratorsIfNeeded(

      g_decorator_factory.load(std::memory_order_acquire));

  return symbolizer;

}

// Set g_cached_symbolize_state to s if it is null, otherwise

// delete s.

static void FreeSymbolizer(Symbolizer *s) {

  Symbolizer *old_cached_symbolizer = nullptr;

  if (!g_cached_symbolizer.compare_exchange_strong(old_cached_symbolizer, s,

                                                   std::memory_order_release,

                                                   std::memory_order_relaxed)) {

    s->~Symbolizer();

    base_internal::LowLevelAlloc::Free(s);

  }

}

Symbolizer::Symbolizer() : ok_(true), addr_map_read_(false) {

  for (SymbolCacheLine &symbol_cache_line : symbol_cache_) {

    for (size_t j = 0; j < std::size(symbol_cache_line.name); ++j) {

      symbol_cache_line.pc[j] = nullptr;

      symbol_cache_line.name[j] = nullptr;

      symbol_cache_line.age[j] = 0;

    }

  }

}

Symbolizer::~Symbolizer() {

  for (SymbolCacheLine &symbol_cache_line : symbol_cache_) {

    for (char *s : symbol_cache_line.name) {

      base_internal::LowLevelAlloc::Free(s);

    }

  }

  ClearAddrMap();

}

void Symbolizer::UpdateDecoratorsIfNeeded(

    SymbolDecorator::Factory* decorator_factory) {

  if (decorator_factory_ == decorator_factory) return;

  for (SymbolCacheLine& symbol_cache_line : symbol_cache_) {

    for (size_t j = 0; j < std::size(symbol_cache_line.name); ++j) {

      symbol_cache_line.pc[j] = nullptr;

      base_internal::LowLevelAlloc::Free(symbol_cache_line.name[j]);

      symbol_cache_line.name[j] = nullptr;

      symbol_cache_line.age[j] = 0;

    }

  }

  decorator_factory_ = decorator_factory;

  for (size_t i = 0, end = addr_map_.Size(); i < end; ++i) {

    ObjFile* obj = addr_map_.At(i);

    obj->decorator.reset();

  }

}

// We don't use assert() since it's not guaranteed to be

// async-signal-safe.  Instead we define a minimal assertion

// macro. So far, we don't need pretty printing for __FILE__, etc.

#define SAFE_ASSERT(expr) ((expr) ? static_cast<void>(0) : abort())

// Read up to "count" bytes from file descriptor "fd" into the buffer

// starting at "buf" while handling short reads and EINTR.  On

// success, return the number of bytes read.  Otherwise, return -1.

static ssize_t ReadPersistent(int fd, void *buf, size_t count) {

  SAFE_ASSERT(fd >= 0);

  SAFE_ASSERT(count <= SSIZE_MAX);

  char *buf0 = reinterpret_cast<char *>(buf);

  size_t num_bytes = 0;

  while (num_bytes < count) {

    ssize_t len;

    NO_INTR(len = read(fd, buf0 + num_bytes, count - num_bytes));

    if (len < 0) {  // There was an error other than EINTR.

      ABSL_RAW_LOG(WARNING, "read failed: errno=%d", errno);

      return -1;

    }

    if (len == 0) {  // Reached EOF.

      break;

    }

    num_bytes += static_cast<size_t>(len);

  }

  SAFE_ASSERT(num_bytes <= count);

  return static_cast<ssize_t>(num_bytes);

}

// Read up to "count" bytes from "offset" into the buffer starting at "buf",

// while handling short reads and EINTR.  On success, return the number of bytes

// read.  Otherwise, return -1.

ssize_t CachingFile::ReadFromOffset(void *buf, size_t count, off_t offset) {

  char *dst = static_cast<char *>(buf);

  size_t read = 0;

  while (read < count) {

    // Look in cache first.

    if (offset >= cache_start_ && offset < cache_limit_) {

      const char *hit_start = &cache_[offset - cache_start_];

      const size_t n =

          std::min(count - read, static_cast<size_t>(cache_limit_ - offset));

      memcpy(dst, hit_start, n);

      dst += n;

      read += static_cast<size_t>(n);

      offset += static_cast<off_t>(n);

      continue;

    }

    cache_start_ = 0;

    cache_limit_ = 0;

    ssize_t n = pread(fd_, cache_, cache_size_, offset);

    if (n < 0) {

      if (errno == EINTR) {

        continue;

      }

      ABSL_RAW_LOG(WARNING, "read failed: errno=%d", errno);

      return -1;

    }

    if (n == 0) {  // Reached EOF.

      break;

    }

    cache_start_ = offset;

    cache_limit_ = offset + static_cast<off_t>(n);

    // Next iteration will copy from cache into dst.

  }

  return static_cast<ssize_t>(read);

}

// Try reading exactly "count" bytes from "offset" bytes into the buffer

// starting at "buf" while handling short reads and EINTR.  On success, return

// true. Otherwise, return false.

bool CachingFile::ReadFromOffsetExact(void *buf, size_t count, off_t offset) {

  ssize_t len = ReadFromOffset(buf, count, offset);

  return len >= 0 && static_cast<size_t>(len) == count;

}

// Returns elf_header.e_type if the file pointed by fd is an ELF binary.

static int FileGetElfType(CachingFile *file) {

  ElfW(Ehdr) elf_header;

  if (!file->ReadFromOffsetExact(&elf_header, sizeof(elf_header), 0)) {

    return -1;

  }

  if (memcmp(elf_header.e_ident, ELFMAG, SELFMAG) != 0) {

    return -1;

  }

  return elf_header.e_type;

}

// Read the section headers in the given ELF binary, and if a section

// of the specified type is found, set the output to this section header

// and return true.  Otherwise, return false.

// To keep stack consumption low, we would like this function to not get

// inlined.

ABSL_ATTRIBUTE_NOINLINE static bool GetSectionHeaderByType(

    CachingFile* file, ElfW(Half) sh_num, const off_t sh_offset,

    ElfW(Word) type, ElfW(Shdr) * out, char* tmp_buf, size_t tmp_buf_size) {

  ElfW(Shdr) *buf = reinterpret_cast<ElfW(Shdr) *>(tmp_buf);

  const size_t buf_entries = tmp_buf_size / sizeof(buf[0]);

  const size_t buf_bytes = buf_entries * sizeof(buf[0]);

  for (size_t i = 0; static_cast<int>(i) < sh_num;) {

    const size_t num_bytes_left =

        (static_cast<size_t>(sh_num) - i) * sizeof(buf[0]);

    const size_t num_bytes_to_read =

        (buf_bytes > num_bytes_left) ? num_bytes_left : buf_bytes;

    const off_t offset = sh_offset + static_cast<off_t>(i * sizeof(buf[0]));

    const ssize_t len = file->ReadFromOffset(buf, num_bytes_to_read, offset);

    if (len <= 0) {

      ABSL_RAW_LOG(WARNING, "Reading %zu bytes from offset %ju returned %zd.",

                   num_bytes_to_read, static_cast<intmax_t>(offset), len);

      return false;

    }

    if (static_cast<size_t>(len) % sizeof(buf[0]) != 0) {

      ABSL_RAW_LOG(

          WARNING,

          "Reading %zu bytes from offset %jd returned %zd which is not a "

          "multiple of %zu.",

          num_bytes_to_read, static_cast<intmax_t>(offset), len,

          sizeof(buf[0]));

      return false;

    }

    const size_t num_headers_in_buf = static_cast<size_t>(len) / sizeof(buf[0]);

    SAFE_ASSERT(num_headers_in_buf <= buf_entries);

    for (size_t j = 0; j < num_headers_in_buf; ++j) {

      if (buf[j].sh_type == type) {

        *out = buf[j];

        return true;

      }

    }

    i += num_headers_in_buf;

  }

  return false;

}

// There is no particular reason to limit section name to 63 characters,

// but there has (as yet) been no need for anything longer either.

const int kMaxSectionNameLen = 64;

// Small cache to use for miscellaneous file reads.

const int kSmallFileCacheSize = 100;

bool ForEachSection(int fd,

                    const std::function<bool(absl::string_view name,

                                             const ElfW(Shdr) &)> &callback) {

  char buf[kSmallFileCacheSize];

  CachingFile file(fd, buf, sizeof(buf));

  ElfW(Ehdr) elf_header;

  if (!file.ReadFromOffsetExact(&elf_header, sizeof(elf_header), 0)) {

    return false;

  }

  // Technically it can be larger, but in practice this never happens.

  if (elf_header.e_shentsize != sizeof(ElfW(Shdr))) {

    return false;

  }

  ElfW(Shdr) shstrtab;

  off_t shstrtab_offset = static_cast<off_t>(elf_header.e_shoff) +

                          elf_header.e_shentsize * elf_header.e_shstrndx;

  if (!file.ReadFromOffsetExact(&shstrtab, sizeof(shstrtab), shstrtab_offset)) {

    return false;

  }

  for (int i = 0; i < elf_header.e_shnum; ++i) {

    ElfW(Shdr) out;

    off_t section_header_offset =

        static_cast<off_t>(elf_header.e_shoff) + elf_header.e_shentsize * i;

    if (!file.ReadFromOffsetExact(&out, sizeof(out), section_header_offset)) {

      return false;

    }

    off_t name_offset = static_cast<off_t>(shstrtab.sh_offset) + out.sh_name;

    char header_name[kMaxSectionNameLen];

    ssize_t n_read =

        file.ReadFromOffset(&header_name, kMaxSectionNameLen, name_offset);

    if (n_read < 0) {

      return false;

    } else if (n_read > kMaxSectionNameLen) {

      // Long read?

      return false;

    }

    absl::string_view name(header_name,

                           strnlen(header_name, static_cast<size_t>(n_read)));

    if (!callback(name, out)) {

      break;

    }

  }

  return true;

}

// name_len should include terminating '\0'.

bool GetSectionHeaderByName(int fd, const char *name, size_t name_len,

                            ElfW(Shdr) * out) {

  char header_name[kMaxSectionNameLen];

  if (sizeof(header_name) < name_len) {

    ABSL_RAW_LOG(WARNING,

                 "Section name '%s' is too long (%zu); "

                 "section will not be found (even if present).",

                 name, name_len);

    // No point in even trying.

    return false;

  }

  char buf[kSmallFileCacheSize];

  CachingFile file(fd, buf, sizeof(buf));

  ElfW(Ehdr) elf_header;

  if (!file.ReadFromOffsetExact(&elf_header, sizeof(elf_header), 0)) {

    return false;

  }

  // Technically it can be larger, but in practice this never happens.

  if (elf_header.e_shentsize != sizeof(ElfW(Shdr))) {

    return false;

  }

  ElfW(Shdr) shstrtab;

  off_t shstrtab_offset = static_cast<off_t>(elf_header.e_shoff) +

                          elf_header.e_shentsize * elf_header.e_shstrndx;

  if (!file.ReadFromOffsetExact(&shstrtab, sizeof(shstrtab), shstrtab_offset)) {

    return false;

  }

  for (int i = 0; i < elf_header.e_shnum; ++i) {

    off_t section_header_offset =

        static_cast<off_t>(elf_header.e_shoff) + elf_header.e_shentsize * i;

    if (!file.ReadFromOffsetExact(out, sizeof(*out), section_header_offset)) {

      return false;

    }

    off_t name_offset = static_cast<off_t>(shstrtab.sh_offset) + out->sh_name;

    ssize_t n_read = file.ReadFromOffset(&header_name, name_len, name_offset);

    if (n_read < 0) {

      return false;

    } else if (static_cast<size_t>(n_read) != name_len) {

      // Short read -- name could be at end of file.

      continue;

    }

    if (memcmp(header_name, name, name_len) == 0) {

      return true;

    }

  }

  return false;

}

// Compare symbols at in the same address.

// Return true if we should pick symbol1.

static bool ShouldPickFirstSymbol(const ElfW(Sym) & symbol1,

                                  const ElfW(Sym) & symbol2) {

  // If one of the symbols is weak and the other is not, pick the one

  // this is not a weak symbol.

  char bind1 = ELF_ST_BIND(symbol1.st_info);

  char bind2 = ELF_ST_BIND(symbol2.st_info);

  if (bind1 == STB_WEAK && bind2 != STB_WEAK) return false;

  if (bind2 == STB_WEAK && bind1 != STB_WEAK) return true;

  // If one of the symbols has zero size and the other is not, pick the

  // one that has non-zero size.

  if (symbol1.st_size != 0 && symbol2.st_size == 0) {

    return true;

  }

  if (symbol1.st_size == 0 && symbol2.st_size != 0) {

    return false;

  }

  // If one of the symbols has no type and the other is not, pick the

  // one that has a type.

  char type1 = ELF_ST_TYPE(symbol1.st_info);

  char type2 = ELF_ST_TYPE(symbol2.st_info);

  if (type1 != STT_NOTYPE && type2 == STT_NOTYPE) {

    return true;

  }

  if (type1 == STT_NOTYPE && type2 != STT_NOTYPE) {

    return false;

  }

  // Pick the first one, if we still cannot decide.

  return true;

}

// Return true if an address is inside a section.

static bool InSection(const void *address, ptrdiff_t relocation,

                      const ElfW(Shdr) * section) {

  const char *start = reinterpret_cast<const char *>(

      section->sh_addr + static_cast<ElfW(Addr)>(relocation));

  size_t size = static_cast<size_t>(section->sh_size);

  return start <= address && address < (start + size);

}

static const char *ComputeOffset(const char *base, ptrdiff_t offset) {

  // Note: cast to intptr_t to avoid undefined behavior when base evaluates to

  // zero and offset is non-zero.

  return reinterpret_cast<const char *>(reinterpret_cast<intptr_t>(base) +

                                        offset);

}

// Read a symbol table and look for the symbol containing the

// pc. Iterate over symbols in a symbol table and look for the symbol

// containing "pc".  If the symbol is found, and its name fits in

// out_size, the name is written into out and SYMBOL_FOUND is returned.

// If the name does not fit, truncated name is written into out,

// and SYMBOL_TRUNCATED is returned. Out is NUL-terminated.

// If the symbol is not found, SYMBOL_NOT_FOUND is returned;

// To keep stack consumption low, we would like this function to not get

// inlined.

ABSL_ATTRIBUTE_NOINLINE static FindSymbolResult FindSymbol(

    const void* const pc, CachingFile* file, char* out, size_t out_size,

    ptrdiff_t relocation, const ElfW(Shdr) * strtab, const ElfW(Shdr) * symtab,

    const ElfW(Shdr) * opd, char* tmp_buf, size_t tmp_buf_size) {

  if (symtab == nullptr) {

    return SYMBOL_NOT_FOUND;

  }

  // In the ELF specification, sh_entsize is a generic section header field that

  // holds the entry size in bytes for sections containing fixed-size entries.

  // For symbol tables (SHT_SYMTAB and SHT_DYNSYM), the ELF specification

  // mandates that each entry is an ElfW(Sym), so sh_entsize should always equal

  // sizeof(ElfW(Sym)).

  //

  // However, because sh_entsize is read directly from the untrusted object

  // file, a crafted or corrupt file can specify an unexpected value:

  // 1. Setting sh_entsize to 0 would cause a division-by-zero (SIGFPE) in the

  //    num_symbols calculation below.

  // 2. Setting sh_entsize to a value other than sizeof(ElfW(Sym)) would

  //    desynchronize our fixed-size ElfW(Sym) buffer reads from the per-entry

  //    stride in the file.

  // Reject such malformed tables, mirroring the e_shentsize check we apply to

  // section headers.

  if (symtab->sh_entsize != sizeof(ElfW(Sym))) {

    return SYMBOL_NOT_FOUND;

  }

  // Read multiple symbols at once to save read() calls.

  ElfW(Sym) *buf = reinterpret_cast<ElfW(Sym) *>(tmp_buf);

  const size_t buf_entries = tmp_buf_size / sizeof(buf[0]);

  const size_t num_symbols = symtab->sh_size / symtab->sh_entsize;

  // On platforms using an .opd section (PowerPC & IA64), a function symbol

  // has the address of a function descriptor, which contains the real

  // starting address.  However, we do not always want to use the real

  // starting address because we sometimes want to symbolize a function

  // pointer into the .opd section, e.g. FindSymbol(&foo,...).

  const bool pc_in_opd = kPlatformUsesOPDSections && opd != nullptr &&

                         InSection(pc, relocation, opd);

  const bool deref_function_descriptor_pointer =

      kPlatformUsesOPDSections && opd != nullptr && !pc_in_opd;

  ElfW(Sym) best_match;

  SafeMemZero(&best_match, sizeof(best_match));

  bool found_match = false;

  for (size_t i = 0; i < num_symbols;) {

    off_t offset =

        static_cast<off_t>(symtab->sh_offset + i * symtab->sh_entsize);

    const size_t num_remaining_symbols = num_symbols - i;

    const size_t entries_in_chunk =

        std::min(num_remaining_symbols, buf_entries);

    const size_t bytes_in_chunk = entries_in_chunk * sizeof(buf[0]);

    const ssize_t len = file->ReadFromOffset(buf, bytes_in_chunk, offset);

    SAFE_ASSERT(len > 0);

    SAFE_ASSERT(static_cast<size_t>(len) % sizeof(buf[0]) == 0);

    const size_t num_symbols_in_buf = static_cast<size_t>(len) / sizeof(buf[0]);

    SAFE_ASSERT(num_symbols_in_buf <= entries_in_chunk);

    for (size_t j = 0; j < num_symbols_in_buf; ++j) {

      const ElfW(Sym) &symbol = buf[j];

      // For a DSO, a symbol address is relocated by the loading address.

      // We keep the original address for opd redirection below.

      const char *const original_start_address =

          reinterpret_cast<const char *>(symbol.st_value);

      const char *start_address =

          ComputeOffset(original_start_address, relocation);

#ifdef __arm__

      // ARM functions are always aligned to multiples of two bytes; the

      // lowest-order bit in start_address is ignored by the CPU and indicates

      // whether the function contains ARM (0) or Thumb (1) code. We don't care

      // about what encoding is being used; we just want the real start address

      // of the function.

      start_address = reinterpret_cast<const char *>(

          reinterpret_cast<uintptr_t>(start_address) & ~1u);

#endif

      if (deref_function_descriptor_pointer &&

          InSection(original_start_address, /*relocation=*/0, opd)) {

        // The opd section is mapped into memory.  Just dereference

        // start_address to get the first double word, which points to the

        // function entry.

        start_address = *reinterpret_cast<const char *const *>(start_address);

      }

      // If pc is inside the .opd section, it points to a function descriptor.

      const size_t size = pc_in_opd ? kFunctionDescriptorSize : symbol.st_size;

      const void *const end_address =

          ComputeOffset(start_address, static_cast<ptrdiff_t>(size));

      if (symbol.st_value != 0 &&  // Skip null value symbols.

          symbol.st_shndx != 0 &&  // Skip undefined symbols.

#ifdef STT_TLS

          ELF_ST_TYPE(symbol.st_info) != STT_TLS &&  // Skip thread-local data.

#endif                                               // STT_TLS

          ((start_address <= pc && pc < end_address) ||

           (start_address == pc && pc == end_address))) {

        if (!found_match || ShouldPickFirstSymbol(symbol, best_match)) {

          found_match = true;

          best_match = symbol;

        }

      }

    }

    i += num_symbols_in_buf;

  }

  if (found_match) {

    const off_t off =

        static_cast<off_t>(strtab->sh_offset) + best_match.st_name;

    const ssize_t n_read = file->ReadFromOffset(out, out_size, off);

    if (n_read <= 0) {

      // This should never happen.

      ABSL_RAW_LOG(WARNING,

                   "Unable to read from fd %d at offset %lld: n_read = %zd",

                   file->fd(), static_cast<long long>(off), n_read);

      return SYMBOL_NOT_FOUND;

    }

    ABSL_RAW_CHECK(static_cast<size_t>(n_read) <= out_size,

                   "ReadFromOffset read too much data.");

    // strtab->sh_offset points into .strtab-like section that contains

    // NUL-terminated strings: '\0foo\0barbaz\0...".

    //

    // sh_offset+st_name points to the start of symbol name, but we don't know

    // how long the symbol is, so we try to read as much as we have space for,

    // and usually over-read (i.e. there is a NUL somewhere before n_read).

    if (memchr(out, '\0', static_cast<size_t>(n_read)) == nullptr) {

      // Either out_size was too small (n_read == out_size and no NUL), or

      // we tried to read past the EOF (n_read < out_size) and .strtab is

      // corrupt (missing terminating NUL; should never happen for valid ELF).

      out[n_read - 1] = '\0';

      return SYMBOL_TRUNCATED;

    }

    return SYMBOL_FOUND;

  }

  return SYMBOL_NOT_FOUND;

}

// Get the symbol name of "pc" from the file pointed by "fd".  Process

// both regular and dynamic symbol tables if necessary.

// See FindSymbol() comment for description of return value.

FindSymbolResult Symbolizer::GetSymbolFromObjectFile(

    const ObjFile &obj, const void *const pc, const ptrdiff_t relocation,

    char *out, size_t out_size, char *tmp_buf, size_t tmp_buf_size) {

  ElfW(Shdr) symtab;

  ElfW(Shdr) strtab;

  ElfW(Shdr) opd;

  ElfW(Shdr) *opd_ptr = nullptr;

  // On platforms using an .opd sections for function descriptor, read

  // the section header.  The .opd section is in data segment and should be

  // loaded but we check that it is mapped just to be extra careful.

  if (kPlatformUsesOPDSections) {

    if (GetSectionHeaderByName(obj.fd, kOpdSectionName,

                               sizeof(kOpdSectionName) - 1, &opd) &&

        FindObjFile(reinterpret_cast<const char *>(opd.sh_addr) + relocation,

                    opd.sh_size) != nullptr) {

      opd_ptr = &opd;

    } else {

      return SYMBOL_NOT_FOUND;

    }

  }

  CachingFile file(obj.fd, file_cache_, sizeof(file_cache_));

  // Consult a regular symbol table, then fall back to the dynamic symbol table.

  for (const auto symbol_table_type : {SHT_SYMTAB, SHT_DYNSYM}) {

    if (!GetSectionHeaderByType(&file, obj.elf_header.e_shnum,

                                static_cast<off_t>(obj.elf_header.e_shoff),

                                static_cast<ElfW(Word)>(symbol_table_type),

                                &symtab, tmp_buf, tmp_buf_size)) {

      continue;

    }

    if (!file.ReadFromOffsetExact(