simpleperf/read_elf.cpp - platform/system/extras - Git at Google

 /*
  * Copyright (C) 2015 The Android Open Source Project
  *
  * 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
  *
  *      http://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.
  */

 #include "read_elf.h"
 #include "read_apk.h"

 #include <stdio.h>
 #include <string.h>
 #include <sys/stat.h>
 #include <sys/types.h>

 #include <algorithm>
 #include <limits>

 #include <android-base/file.h>
 #include <android-base/logging.h>

 #pragma clang diagnostic push
 #pragma clang diagnostic ignored "-Wunused-parameter"

 #include <llvm/ADT/StringRef.h>
 #include <llvm/Object/ELFObjectFile.h>
 #include <llvm/Object/ObjectFile.h>

 #pragma clang diagnostic pop

 #include "JITDebugReader.h"
 #include "utils.h"

 namespace simpleperf {

 const static char* ELF_NOTE_GNU = "GNU";
 const static int NT_GNU_BUILD_ID = 3;

 std::ostream& operator<<(std::ostream& os, const ElfStatus& status) {
   switch (status) {
     case ElfStatus::NO_ERROR:
       os << "No error";
       break;
     case ElfStatus::FILE_NOT_FOUND:
       os << "File not found";
       break;
     case ElfStatus::READ_FAILED:
       os << "Read failed";
       break;
     case ElfStatus::FILE_MALFORMED:
       os << "Malformed file";
       break;
     case ElfStatus::NO_SYMBOL_TABLE:
       os << "No symbol table";
       break;
     case ElfStatus::NO_BUILD_ID:
       os << "No build id";
       break;
     case ElfStatus::BUILD_ID_MISMATCH:
       os << "Build id mismatch";
       break;
     case ElfStatus::SECTION_NOT_FOUND:
       os << "Section not found";
       break;
   }
   return os;
 }

 bool IsValidElfFileMagic(const char* buf, size_t buf_size) {
   static const char elf_magic[] = {0x7f, 'E', 'L', 'F'};
   return (buf_size >= 4u && memcmp(buf, elf_magic, 4) == 0);
 }

 ElfStatus IsValidElfFile(int fd, uint64_t file_offset) {
   char buf[4];
   if (!android::base::ReadFullyAtOffset(fd, buf, 4, file_offset)) {
     return ElfStatus::READ_FAILED;
   }
   return IsValidElfFileMagic(buf, 4) ? ElfStatus::NO_ERROR : ElfStatus::FILE_MALFORMED;
 }

 bool GetBuildIdFromNoteSection(const char* section, size_t section_size, BuildId* build_id) {
   const char* p = section;
   const char* end = p + section_size;
   while (p < end) {
     if (p + 12 >= end) {
       return false;
     }
     uint32_t namesz;
     uint32_t descsz;
     uint32_t type;
     MoveFromBinaryFormat(namesz, p);
     MoveFromBinaryFormat(descsz, p);
     MoveFromBinaryFormat(type, p);
     namesz = Align(namesz, 4);
     descsz = Align(descsz, 4);
     if ((type == NT_GNU_BUILD_ID) && (p < end) && (strcmp(p, ELF_NOTE_GNU) == 0)) {
       const char* desc_start = p + namesz;
       const char* desc_end = desc_start + descsz;
       if (desc_start > p && desc_start < desc_end && desc_end <= end) {
         *build_id = BuildId(p + namesz, descsz);
         return true;
       } else {
         return false;
       }
     }
     p += namesz + descsz;
   }
   return false;
 }

 ElfStatus GetBuildIdFromNoteFile(const std::string& filename, BuildId* build_id) {
   std::string content;
   if (!android::base::ReadFileToString(filename, &content)) {
     return ElfStatus::READ_FAILED;
   }
   if (!GetBuildIdFromNoteSection(content.c_str(), content.size(), build_id)) {
     return ElfStatus::NO_BUILD_ID;
   }
   return ElfStatus::NO_ERROR;
 }

 bool IsArmMappingSymbol(const char* name) {
   // Mapping symbols in arm, which are described in "ELF for ARM Architecture" and
   // "ELF for ARM 64-bit Architecture". The regular expression to match mapping symbol
   // is ^\$(a|d|t|x)(\..*)?$
   return name[0] == '$' && strchr("adtx", name[1]) != nullptr &&
          (name[2] == '\0' || name[2] == '.');
 }

 namespace {

 struct BinaryWrapper {
   std::unique_ptr<llvm::MemoryBuffer> buffer;
   std::unique_ptr<llvm::object::ObjectFile> obj;
 };

 static ElfStatus OpenObjectFile(const std::string& filename, uint64_t file_offset,
                                 uint64_t file_size, BinaryWrapper* wrapper) {
   if (!IsRegularFile(filename)) {
     return ElfStatus::FILE_NOT_FOUND;
   }
   android::base::unique_fd fd = FileHelper::OpenReadOnly(filename);
   if (fd == -1) {
     return ElfStatus::READ_FAILED;
   }
   if (file_size == 0) {
     file_size = GetFileSize(filename);
     if (file_size == 0) {
       return ElfStatus::READ_FAILED;
     }
   }
   ElfStatus status = IsValidElfFile(fd, file_offset);
   if (status != ElfStatus::NO_ERROR) {
     return status;
   }
   auto buffer_or_err = llvm::MemoryBuffer::getFileSlice(filename, file_size, file_offset);
   if (!buffer_or_err) {
     return ElfStatus::READ_FAILED;
   }
   auto obj_or_err =
       llvm::object::ObjectFile::createObjectFile(buffer_or_err.get()->getMemBufferRef());
   if (!obj_or_err) {
     return ElfStatus::READ_FAILED;
   }
   wrapper->buffer = std::move(buffer_or_err.get());
   wrapper->obj = std::move(obj_or_err.get());
   return ElfStatus::NO_ERROR;
 }

 static ElfStatus OpenObjectFileInMemory(const char* data, size_t size, BinaryWrapper* wrapper) {
   auto buffer = llvm::MemoryBuffer::getMemBuffer(llvm::StringRef(data, size));
   auto obj_or_err = llvm::object::ObjectFile::createObjectFile(buffer->getMemBufferRef());
   if (!obj_or_err) {
     return ElfStatus::FILE_MALFORMED;
   }
   wrapper->buffer = std::move(buffer);
   wrapper->obj = std::move(obj_or_err.get());
   return ElfStatus::NO_ERROR;
 }

 static inline llvm::Expected<uint32_t> GetSymbolFlags(const llvm::object::ELFSymbolRef& symbol) {
   return symbol.getFlags();
 }

 static inline llvm::Expected<uint64_t> GetSymbolValue(const llvm::object::ELFSymbolRef& symbol) {
   return symbol.getValue();
 }

 static inline llvm::Expected<llvm::StringRef> GetSectionName(
     const llvm::object::SectionRef& section) {
   return section.getName();
 }

 static inline llvm::Expected<llvm::StringRef> GetSectionContents(
     const llvm::object::SectionRef& section) {
   return section.getContents();
 }

 template <typename ELFT>
 static inline const llvm::object::ELFFile<ELFT>* GetELFFile(
     const llvm::object::ELFObjectFile<ELFT>* obj) {
   return &obj->getELFFile();
 }

 template <typename ELFT>
 static inline const typename ELFT::Ehdr& GetELFHeader(const llvm::object::ELFFile<ELFT>* elf) {
   return elf->getHeader();
 }

 template <typename ELFT>
 static inline llvm::Expected<typename ELFT::PhdrRange> GetELFProgramHeaders(
     const llvm::object::ELFFile<ELFT>* elf) {
   return elf->program_headers();
 }

 template <typename ELFT>
 static inline llvm::Expected<llvm::StringRef> GetELFSectionName(
     const llvm::object::ELFFile<ELFT>* elf, const typename ELFT::Shdr& section_header) {
   return elf->getSectionName(section_header);
 }

 void ReadSymbolTable(llvm::object::symbol_iterator sym_begin, llvm::object::symbol_iterator sym_end,
                      const std::function<void(const ElfFileSymbol&)>& callback, bool is_arm,
                      const llvm::object::section_iterator& section_end) {
   for (; sym_begin != sym_end; ++sym_begin) {
     ElfFileSymbol symbol;
     auto symbol_ref = static_cast<const llvm::object::ELFSymbolRef*>(&*sym_begin);
     // Exclude undefined symbols, otherwise we may wrongly use them as labels in functions.
     if (auto flags = GetSymbolFlags(*symbol_ref);
         !flags || (flags.get() & symbol_ref->SF_Undefined)) {
       continue;
     }
     llvm::Expected<llvm::object::section_iterator> section_it_or_err = symbol_ref->getSection();
     if (!section_it_or_err) {
       continue;
     }
     // Symbols in .dynsym section don't have associated section.
     if (section_it_or_err.get() != section_end) {
       llvm::Expected<llvm::StringRef> section_name = GetSectionName(*section_it_or_err.get());
       if (!section_name || section_name.get().empty()) {
         continue;
       }
       if (section_name.get() == ".text") {
         symbol.is_in_text_section = true;
       }
     }

     llvm::Expected<llvm::StringRef> symbol_name_or_err = symbol_ref->getName();
     if (!symbol_name_or_err || symbol_name_or_err.get().empty()) {
       continue;
     }

     symbol.name = symbol_name_or_err.get();
     llvm::Expected<uint64_t> symbol_value = GetSymbolValue(*symbol_ref);
     if (!symbol_value) {
       continue;
     }
     symbol.vaddr = symbol_value.get();
     if ((symbol.vaddr & 1) != 0 && is_arm) {
       // Arm sets bit 0 to mark it as thumb code, remove the flag.
       symbol.vaddr &= ~1;
     }
     symbol.len = symbol_ref->getSize();
     llvm::object::SymbolRef::Type symbol_type = *symbol_ref->getType();
     if (symbol_type == llvm::object::SymbolRef::ST_Function) {
       symbol.is_func = true;
     } else if (symbol_type == llvm::object::SymbolRef::ST_Unknown) {
       if (symbol.is_in_text_section) {
         symbol.is_label = true;
         if (is_arm) {
           // Remove mapping symbols in arm.
           const char* p = (symbol.name.compare(0, linker_prefix.size(), linker_prefix) == 0)
                               ? symbol.name.c_str() + linker_prefix.size()
                               : symbol.name.c_str();
           if (IsArmMappingSymbol(p)) {
             symbol.is_label = false;
           }
         }
       }
     }

     callback(symbol);
   }
 }

 template <class ELFT>
 void AddSymbolForPltSection(const llvm::object::ELFObjectFile<ELFT>* elf,
                             const std::function<void(const ElfFileSymbol&)>& callback) {
   // We may sample instructions in .plt section if the program
   // calls functions from shared libraries. Different architectures use
   // different formats to store .plt section, so it needs a lot of work to match
   // instructions in .plt section to symbols. As samples in .plt section rarely
   // happen, and .plt section can hardly be a performance bottleneck, we can
   // just use a symbol @plt to represent instructions in .plt section.
   for (auto it = elf->section_begin(); it != elf->section_end(); ++it) {
     const llvm::object::ELFSectionRef& section_ref = *it;
     llvm::Expected<llvm::StringRef> section_name = GetSectionName(section_ref);
     if (!section_name || section_name.get() != ".plt") {
       continue;
     }
     const auto* shdr = elf->getSection(section_ref.getRawDataRefImpl());
     if (shdr == nullptr) {
       return;
     }
     ElfFileSymbol symbol;
     symbol.vaddr = shdr->sh_addr;
     symbol.len = shdr->sh_size;
     symbol.is_func = true;
     symbol.is_label = true;
     symbol.is_in_text_section = true;
     symbol.name = "@plt";
     callback(symbol);
     return;
   }
 }

 template <class ELFT>
 void CheckSymbolSections(const llvm::object::ELFObjectFile<ELFT>* elf, bool* has_symtab,
                          bool* has_dynsym) {
   *has_symtab = false;
   *has_dynsym = false;
   for (auto it = elf->section_begin(); it != elf->section_end(); ++it) {
     const llvm::object::ELFSectionRef& section_ref = *it;
     llvm::Expected<llvm::StringRef> section_name = GetSectionName(section_ref);
     if (!section_name) {
       continue;
     }
     if (section_name.get() == ".dynsym") {
       *has_dynsym = true;
     } else if (section_name.get() == ".symtab") {
       *has_symtab = true;
     }
   }
 }

 template <typename T>
 class ElfFileImpl {};

 template <typename ELFT>
 class ElfFileImpl<llvm::object::ELFObjectFile<ELFT>> : public ElfFile {
  public:
   ElfFileImpl(BinaryWrapper&& wrapper, const llvm::object::ELFObjectFile<ELFT>* elf_obj)
       : wrapper_(std::move(wrapper)), elf_obj_(elf_obj), elf_(GetELFFile(elf_obj_)) {}

   bool Is64Bit() override { return GetELFHeader(elf_).getFileClass() == llvm::ELF::ELFCLASS64; }

   llvm::MemoryBuffer* GetMemoryBuffer() override { return wrapper_.buffer.get(); }

   std::vector<ElfSegment> GetProgramHeader() override {
     auto program_headers = GetELFProgramHeaders(elf_);
     if (!program_headers) {
       return {};
     }
     std::vector<ElfSegment> segments(program_headers.get().size());
     for (size_t i = 0; i < program_headers.get().size(); i++) {
       const auto& phdr = program_headers.get()[i];
       segments[i].vaddr = phdr.p_vaddr;
       segments[i].file_offset = phdr.p_offset;
       segments[i].file_size = phdr.p_filesz;
       segments[i].is_executable =
           (phdr.p_type == llvm::ELF::PT_LOAD) && (phdr.p_flags & llvm::ELF::PF_X);
       segments[i].is_load = (phdr.p_type == llvm::ELF::PT_LOAD);
     }
     return segments;
   }

   std::vector<ElfSection> GetSectionHeader() override {
     auto section_headers_or_err = elf_->sections();
     if (!section_headers_or_err) {
       return {};
     }
     const auto& section_headers = section_headers_or_err.get();
     std::vector<ElfSection> sections(section_headers.size());
     for (size_t i = 0; i < section_headers.size(); i++) {
       const auto& shdr = section_headers[i];
       if (auto name = GetELFSectionName(elf_, shdr); name) {
         sections[i].name = name.get();
       }
       sections[i].vaddr = shdr.sh_addr;
       sections[i].file_offset = shdr.sh_offset;
       sections[i].size = shdr.sh_size;
     }
     return sections;
   }

   ElfStatus GetBuildId(BuildId* build_id) override {
     llvm::StringRef data = elf_obj_->getData();
     const char* binary_start = data.data();
     const char* binary_end = data.data() + data.size();
     for (auto it = elf_obj_->section_begin(); it != elf_obj_->section_end(); ++it) {
       const llvm::object::ELFSectionRef& section_ref = *it;
       if (section_ref.getType() == llvm::ELF::SHT_NOTE) {
         llvm::Expected<llvm::StringRef> content = GetSectionContents(section_ref);
         if (!content) {
           return ElfStatus::NO_BUILD_ID;
         }
         const llvm::StringRef& data = content.get();
         if (data.data() < binary_start || data.data() + data.size() > binary_end) {
           return ElfStatus::NO_BUILD_ID;
         }
         if (GetBuildIdFromNoteSection(data.data(), data.size(), build_id)) {
           return ElfStatus::NO_ERROR;
         }
       }
     }
     return ElfStatus::NO_BUILD_ID;
   }

   ElfStatus ParseSymbols(const ParseSymbolCallback& callback) override {
     auto machine = GetELFHeader(elf_).e_machine;
     bool is_arm = (machine == llvm::ELF::EM_ARM || machine == llvm::ELF::EM_AARCH64);
     AddSymbolForPltSection(elf_obj_, callback);
     // Some applications deliberately ship elf files with broken section tables.
     // So check the existence of .symtab section and .dynsym section before reading symbols.
     bool has_symtab;
     bool has_dynsym;
     CheckSymbolSections(elf_obj_, &has_symtab, &has_dynsym);
     if (has_symtab && elf_obj_->symbol_begin() != elf_obj_->symbol_end()) {
       ReadSymbolTable(elf_obj_->symbol_begin(), elf_obj_->symbol_end(), callback, is_arm,
                       elf_obj_->section_end());
       return ElfStatus::NO_ERROR;
     } else if (has_dynsym && elf_obj_->dynamic_symbol_begin()->getRawDataRefImpl() !=
                                  llvm::object::DataRefImpl()) {
       ReadSymbolTable(elf_obj_->dynamic_symbol_begin(), elf_obj_->dynamic_symbol_end(), callback,
                       is_arm, elf_obj_->section_end());
     }
     std::string debugdata;
     ElfStatus result = ReadSection(".gnu_debugdata", &debugdata);
     if (result == ElfStatus::SECTION_NOT_FOUND) {
       return ElfStatus::NO_SYMBOL_TABLE;
     } else if (result == ElfStatus::NO_ERROR) {
       std::string decompressed_data;
       if (XzDecompress(debugdata, &decompressed_data)) {
         auto debugdata_elf =
             ElfFile::Open(decompressed_data.data(), decompressed_data.size(), &result);
         if (debugdata_elf) {
           return debugdata_elf->ParseSymbols(callback);
         }
       }
     }
     return result;
   }

   void ParseDynamicSymbols(const ParseSymbolCallback& callback) override {
     auto machine = GetELFHeader(elf_).e_machine;
     bool is_arm = (machine == llvm::ELF::EM_ARM || machine == llvm::ELF::EM_AARCH64);
     ReadSymbolTable(elf_obj_->dynamic_symbol_begin(), elf_obj_->dynamic_symbol_end(), callback,
                     is_arm, elf_obj_->section_end());
   }

   ElfStatus ReadSection(const std::string& section_name, std::string* content) override {
     for (llvm::object::section_iterator it = elf_obj_->section_begin();
          it != elf_obj_->section_end(); ++it) {
       llvm::Expected<llvm::StringRef> name = GetSectionName(*it);
       if (!name || name.get() != section_name) {
         continue;
       }
       llvm::Expected<llvm::StringRef> data = GetSectionContents(*it);
       if (!data) {
         return ElfStatus::READ_FAILED;
       }
       *content = data.get();
       return ElfStatus::NO_ERROR;
     }
     return ElfStatus::SECTION_NOT_FOUND;
   }

   uint64_t ReadMinExecutableVaddr(uint64_t* file_offset) {
     bool has_vaddr = false;
     uint64_t min_addr = std::numeric_limits<uint64_t>::max();
     auto program_headers = GetELFProgramHeaders(elf_);
     if (program_headers) {
       for (const auto& ph : program_headers.get()) {
         if ((ph.p_type == llvm::ELF::PT_LOAD) && (ph.p_flags & llvm::ELF::PF_X) &&
             (ph.p_vaddr < min_addr)) {
           min_addr = ph.p_vaddr;
           *file_offset = ph.p_offset;
           has_vaddr = true;
         }
       }
     }
     if (!has_vaddr) {
       // JIT symfiles don't have program headers.
       min_addr = 0;
       *file_offset = 0;
     }
     return min_addr;
   }

   bool VaddrToOff(uint64_t vaddr, uint64_t* file_offset) override {
     auto program_headers = GetELFProgramHeaders(elf_);
     if (!program_headers) {
       return false;
     }
     for (const auto& ph : program_headers.get()) {
       if (ph.p_type == llvm::ELF::PT_LOAD && vaddr >= ph.p_vaddr &&
           vaddr < ph.p_vaddr + ph.p_filesz) {
         *file_offset = vaddr - ph.p_vaddr + ph.p_offset;
         return true;
       }
     }
     return false;
   }

  private:
   BinaryWrapper wrapper_;
   const llvm::object::ELFObjectFile<ELFT>* elf_obj_;
   const llvm::object::ELFFile<ELFT>* elf_;
 };

 std::unique_ptr<ElfFile> CreateElfFileImpl(BinaryWrapper&& wrapper, ElfStatus* status) {
   if (auto obj = llvm::dyn_cast<llvm::object::ELF32LEObjectFile>(wrapper.obj.get())) {
     return std::unique_ptr<ElfFile>(
         new ElfFileImpl<llvm::object::ELF32LEObjectFile>(std::move(wrapper), obj));
   }
   if (auto obj = llvm::dyn_cast<llvm::object::ELF64LEObjectFile>(wrapper.obj.get())) {
     return std::unique_ptr<ElfFile>(
         new ElfFileImpl<llvm::object::ELF64LEObjectFile>(std::move(wrapper), obj));
   }
   *status = ElfStatus::FILE_MALFORMED;
   return nullptr;
 }

 }  // namespace

 std::unique_ptr<ElfFile> ElfFile::Open(const std::string& filename) {
   ElfStatus status;
   auto elf = Open(filename, &status);
   if (!elf) {
     LOG(ERROR) << "failed to open " << filename << ": " << status;
   }
   return elf;
 }

 std::unique_ptr<ElfFile> ElfFile::Open(const std::string& filename,
                                        const BuildId* expected_build_id, ElfStatus* status) {
   BinaryWrapper wrapper;
   auto tuple = SplitUrlInApk(filename);
   if (std::get<0>(tuple)) {
     EmbeddedElf* elf = ApkInspector::FindElfInApkByName(std::get<1>(tuple), std::get<2>(tuple));
     if (elf == nullptr) {
       *status = ElfStatus::FILE_NOT_FOUND;
     } else {
       *status = OpenObjectFile(elf->filepath(), elf->entry_offset(), elf->entry_size(), &wrapper);
     }
   } else if (JITDebugReader::IsPathInJITSymFile(filename)) {
     size_t colon_pos = filename.rfind(':');
     CHECK_NE(colon_pos, std::string::npos);
     // path generated by JITDebugReader: app_jit_cache:<file_start>-<file_end>
     uint64_t file_start;
     uint64_t file_end;
     if (sscanf(filename.data() + colon_pos, ":%" PRIu64 "-%" PRIu64, &file_start, &file_end) != 2) {
       *status = ElfStatus::FILE_NOT_FOUND;
       return nullptr;
     }
     *status =
         OpenObjectFile(filename.substr(0, colon_pos), file_start, file_end - file_start, &wrapper);
   } else {
     *status = OpenObjectFile(filename, 0, 0, &wrapper);
   }
   if (*status != ElfStatus::NO_ERROR) {
     return nullptr;
   }
   auto elf = CreateElfFileImpl(std::move(wrapper), status);
   if (elf && expected_build_id != nullptr && !expected_build_id->IsEmpty()) {
     BuildId real_build_id;
     *status = elf->GetBuildId(&real_build_id);
     if (*status != ElfStatus::NO_ERROR) {
       return nullptr;
     }
     if (*expected_build_id != real_build_id) {
       *status = ElfStatus::BUILD_ID_MISMATCH;
       return nullptr;
     }
   }
   return elf;
 }

 std::unique_ptr<ElfFile> ElfFile::Open(const char* data, size_t size, ElfStatus* status) {
   BinaryWrapper wrapper;
   *status = OpenObjectFileInMemory(data, size, &wrapper);
   if (*status != ElfStatus::NO_ERROR) {
     return nullptr;
   }
   return CreateElfFileImpl(std::move(wrapper), status);
 }

 }  // namespace simpleperf

 // LLVM libraries uses ncurses library, but that isn't needed by simpleperf.
 // So support a naive implementation to avoid depending on ncurses.
 __attribute__((weak)) extern "C" int setupterm(char*, int, int*) {
   return -1;
 }

 __attribute__((weak)) extern "C" struct term* set_curterm(struct term*) {
   return nullptr;
 }

 __attribute__((weak)) extern "C" int del_curterm(struct term*) {
   return -1;
 }

 __attribute__((weak)) extern "C" int tigetnum(char*) {
   return -1;
 }
	/*
	* Copyright (C) 2015 The Android Open Source Project
	*
	* 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
	*
	* http://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.
	*/

	#include "read_elf.h"
	#include "read_apk.h"

	#include <stdio.h>
	#include <string.h>
	#include <sys/stat.h>
	#include <sys/types.h>

	#include <algorithm>
	#include <limits>

	#include <android-base/file.h>
	#include <android-base/logging.h>

	#pragma clang diagnostic push
	#pragma clang diagnostic ignored "-Wunused-parameter"

	#include <llvm/ADT/StringRef.h>
	#include <llvm/Object/ELFObjectFile.h>
	#include <llvm/Object/ObjectFile.h>

	#pragma clang diagnostic pop

	#include "JITDebugReader.h"
	#include "utils.h"

	namespace simpleperf {

	const static char* ELF_NOTE_GNU = "GNU";
	const static int NT_GNU_BUILD_ID = 3;

	std::ostream& operator<<(std::ostream& os, const ElfStatus& status) {
	switch (status) {
	case ElfStatus::NO_ERROR:
	os << "No error";
	break;
	case ElfStatus::FILE_NOT_FOUND:
	os << "File not found";
	break;
	case ElfStatus::READ_FAILED:
	os << "Read failed";
	break;
	case ElfStatus::FILE_MALFORMED:
	os << "Malformed file";
	break;
	case ElfStatus::NO_SYMBOL_TABLE:
	os << "No symbol table";
	break;
	case ElfStatus::NO_BUILD_ID:
	os << "No build id";
	break;
	case ElfStatus::BUILD_ID_MISMATCH:
	os << "Build id mismatch";
	break;
	case ElfStatus::SECTION_NOT_FOUND:
	os << "Section not found";
	break;
	}
	return os;
	}

	bool IsValidElfFileMagic(const char* buf, size_t buf_size) {
	static const char elf_magic[] = {0x7f, 'E', 'L', 'F'};
	return (buf_size >= 4u && memcmp(buf, elf_magic, 4) == 0);
	}

	ElfStatus IsValidElfFile(int fd, uint64_t file_offset) {
	char buf[4];
	if (!android::base::ReadFullyAtOffset(fd, buf, 4, file_offset)) {
	return ElfStatus::READ_FAILED;
	}
	return IsValidElfFileMagic(buf, 4) ? ElfStatus::NO_ERROR : ElfStatus::FILE_MALFORMED;
	}

	bool GetBuildIdFromNoteSection(const char* section, size_t section_size, BuildId* build_id) {
	const char* p = section;
	const char* end = p + section_size;
	while (p < end) {
	if (p + 12 >= end) {
	return false;
	}
	uint32_t namesz;
	uint32_t descsz;
	uint32_t type;
	MoveFromBinaryFormat(namesz, p);
	MoveFromBinaryFormat(descsz, p);
	MoveFromBinaryFormat(type, p);
	namesz = Align(namesz, 4);
	descsz = Align(descsz, 4);
	if ((type == NT_GNU_BUILD_ID) && (p < end) && (strcmp(p, ELF_NOTE_GNU) == 0)) {
	const char* desc_start = p + namesz;
	const char* desc_end = desc_start + descsz;
	if (desc_start > p && desc_start < desc_end && desc_end <= end) {
	*build_id = BuildId(p + namesz, descsz);
	return true;
	} else {
	return false;
	}
	}
	p += namesz + descsz;
	}
	return false;
	}

	ElfStatus GetBuildIdFromNoteFile(const std::string& filename, BuildId* build_id) {
	std::string content;
	if (!android::base::ReadFileToString(filename, &content)) {
	return ElfStatus::READ_FAILED;
	}
	if (!GetBuildIdFromNoteSection(content.c_str(), content.size(), build_id)) {
	return ElfStatus::NO_BUILD_ID;
	}
	return ElfStatus::NO_ERROR;
	}

	bool IsArmMappingSymbol(const char* name) {
	// Mapping symbols in arm, which are described in "ELF for ARM Architecture" and
	// "ELF for ARM 64-bit Architecture". The regular expression to match mapping symbol
	// is ^\$(a\|d\|t\|x)(\..*)?$
	return name[0] == '$' && strchr("adtx", name[1]) != nullptr &&
	(name[2] == '\0' \|\| name[2] == '.');
	}

	namespace {

	struct BinaryWrapper {
	std::unique_ptr<llvm::MemoryBuffer> buffer;
	std::unique_ptr<llvm::object::ObjectFile> obj;
	};

	static ElfStatus OpenObjectFile(const std::string& filename, uint64_t file_offset,
	uint64_t file_size, BinaryWrapper* wrapper) {
	if (!IsRegularFile(filename)) {
	return ElfStatus::FILE_NOT_FOUND;
	}
	android::base::unique_fd fd = FileHelper::OpenReadOnly(filename);
	if (fd == -1) {
	return ElfStatus::READ_FAILED;
	}
	if (file_size == 0) {
	file_size = GetFileSize(filename);
	if (file_size == 0) {
	return ElfStatus::READ_FAILED;
	}
	}
	ElfStatus status = IsValidElfFile(fd, file_offset);
	if (status != ElfStatus::NO_ERROR) {
	return status;
	}
	auto buffer_or_err = llvm::MemoryBuffer::getFileSlice(filename, file_size, file_offset);
	if (!buffer_or_err) {
	return ElfStatus::READ_FAILED;
	}
	auto obj_or_err =
	llvm::object::ObjectFile::createObjectFile(buffer_or_err.get()->getMemBufferRef());
	if (!obj_or_err) {
	return ElfStatus::READ_FAILED;
	}
	wrapper->buffer = std::move(buffer_or_err.get());
	wrapper->obj = std::move(obj_or_err.get());
	return ElfStatus::NO_ERROR;
	}

	static ElfStatus OpenObjectFileInMemory(const char* data, size_t size, BinaryWrapper* wrapper) {
	auto buffer = llvm::MemoryBuffer::getMemBuffer(llvm::StringRef(data, size));
	auto obj_or_err = llvm::object::ObjectFile::createObjectFile(buffer->getMemBufferRef());
	if (!obj_or_err) {
	return ElfStatus::FILE_MALFORMED;
	}
	wrapper->buffer = std::move(buffer);
	wrapper->obj = std::move(obj_or_err.get());
	return ElfStatus::NO_ERROR;
	}

	static inline llvm::Expected<uint32_t> GetSymbolFlags(const llvm::object::ELFSymbolRef& symbol) {
	return symbol.getFlags();
	}

	static inline llvm::Expected<uint64_t> GetSymbolValue(const llvm::object::ELFSymbolRef& symbol) {
	return symbol.getValue();
	}

	static inline llvm::Expected<llvm::StringRef> GetSectionName(
	const llvm::object::SectionRef& section) {
	return section.getName();
	}

	static inline llvm::Expected<llvm::StringRef> GetSectionContents(
	const llvm::object::SectionRef& section) {
	return section.getContents();
	}

	template <typename ELFT>
	static inline const llvm::object::ELFFile<ELFT>* GetELFFile(
	const llvm::object::ELFObjectFile<ELFT>* obj) {
	return &obj->getELFFile();
	}

	template <typename ELFT>
	static inline const typename ELFT::Ehdr& GetELFHeader(const llvm::object::ELFFile<ELFT>* elf) {
	return elf->getHeader();
	}

	template <typename ELFT>
	static inline llvm::Expected<typename ELFT::PhdrRange> GetELFProgramHeaders(
	const llvm::object::ELFFile<ELFT>* elf) {
	return elf->program_headers();
	}

	template <typename ELFT>
	static inline llvm::Expected<llvm::StringRef> GetELFSectionName(
	const llvm::object::ELFFile<ELFT>* elf, const typename ELFT::Shdr& section_header) {
	return elf->getSectionName(section_header);
	}

	void ReadSymbolTable(llvm::object::symbol_iterator sym_begin, llvm::object::symbol_iterator sym_end,
	const std::function<void(const ElfFileSymbol&)>& callback, bool is_arm,
	const llvm::object::section_iterator& section_end) {
	for (; sym_begin != sym_end; ++sym_begin) {
	ElfFileSymbol symbol;
	auto symbol_ref = static_cast<const llvm::object::ELFSymbolRef>(&sym_begin);
	// Exclude undefined symbols, otherwise we may wrongly use them as labels in functions.
	if (auto flags = GetSymbolFlags(*symbol_ref);
	!flags \|\| (flags.get() & symbol_ref->SF_Undefined)) {
	continue;
	}
	llvm::Expected<llvm::object::section_iterator> section_it_or_err = symbol_ref->getSection();
	if (!section_it_or_err) {
	continue;
	}
	// Symbols in .dynsym section don't have associated section.
	if (section_it_or_err.get() != section_end) {
	llvm::Expected<llvm::StringRef> section_name = GetSectionName(*section_it_or_err.get());
	if (!section_name \|\| section_name.get().empty()) {
	continue;
	}
	if (section_name.get() == ".text") {
	symbol.is_in_text_section = true;
	}
	}

	llvm::Expected<llvm::StringRef> symbol_name_or_err = symbol_ref->getName();
	if (!symbol_name_or_err \|\| symbol_name_or_err.get().empty()) {
	continue;
	}

	symbol.name = symbol_name_or_err.get();
	llvm::Expected<uint64_t> symbol_value = GetSymbolValue(*symbol_ref);
	if (!symbol_value) {
	continue;
	}
	symbol.vaddr = symbol_value.get();
	if ((symbol.vaddr & 1) != 0 && is_arm) {
	// Arm sets bit 0 to mark it as thumb code, remove the flag.
	symbol.vaddr &= ~1;
	}
	symbol.len = symbol_ref->getSize();
	llvm::object::SymbolRef::Type symbol_type = *symbol_ref->getType();
	if (symbol_type == llvm::object::SymbolRef::ST_Function) {
	symbol.is_func = true;
	} else if (symbol_type == llvm::object::SymbolRef::ST_Unknown) {
	if (symbol.is_in_text_section) {
	symbol.is_label = true;
	if (is_arm) {
	// Remove mapping symbols in arm.
	const char* p = (symbol.name.compare(0, linker_prefix.size(), linker_prefix) == 0)
	? symbol.name.c_str() + linker_prefix.size()
	: symbol.name.c_str();
	if (IsArmMappingSymbol(p)) {
	symbol.is_label = false;
	}
	}
	}
	}

	callback(symbol);
	}
	}

	template <class ELFT>
	void AddSymbolForPltSection(const llvm::object::ELFObjectFile<ELFT>* elf,
	const std::function<void(const ElfFileSymbol&)>& callback) {
	// We may sample instructions in .plt section if the program
	// calls functions from shared libraries. Different architectures use
	// different formats to store .plt section, so it needs a lot of work to match
	// instructions in .plt section to symbols. As samples in .plt section rarely
	// happen, and .plt section can hardly be a performance bottleneck, we can
	// just use a symbol @plt to represent instructions in .plt section.
	for (auto it = elf->section_begin(); it != elf->section_end(); ++it) {
	const llvm::object::ELFSectionRef& section_ref = *it;
	llvm::Expected<llvm::StringRef> section_name = GetSectionName(section_ref);
	if (!section_name \|\| section_name.get() != ".plt") {
	continue;
	}
	const auto* shdr = elf->getSection(section_ref.getRawDataRefImpl());
	if (shdr == nullptr) {
	return;
	}
	ElfFileSymbol symbol;
	symbol.vaddr = shdr->sh_addr;
	symbol.len = shdr->sh_size;
	symbol.is_func = true;
	symbol.is_label = true;
	symbol.is_in_text_section = true;
	symbol.name = "@plt";
	callback(symbol);
	return;
	}
	}

	template <class ELFT>
	void CheckSymbolSections(const llvm::object::ELFObjectFile<ELFT>* elf, bool* has_symtab,
	bool* has_dynsym) {
	*has_symtab = false;
	*has_dynsym = false;
	for (auto it = elf->section_begin(); it != elf->section_end(); ++it) {
	const llvm::object::ELFSectionRef& section_ref = *it;
	llvm::Expected<llvm::StringRef> section_name = GetSectionName(section_ref);
	if (!section_name) {
	continue;
	}
	if (section_name.get() == ".dynsym") {
	*has_dynsym = true;
	} else if (section_name.get() == ".symtab") {
	*has_symtab = true;
	}
	}
	}

	template <typename T>
	class ElfFileImpl {};

	template <typename ELFT>
	class ElfFileImpl<llvm::object::ELFObjectFile<ELFT>> : public ElfFile {
	public:
	ElfFileImpl(BinaryWrapper&& wrapper, const llvm::object::ELFObjectFile<ELFT>* elf_obj)
	: wrapper_(std::move(wrapper)), elf_obj_(elf_obj), elf_(GetELFFile(elf_obj_)) {}

	bool Is64Bit() override { return GetELFHeader(elf_).getFileClass() == llvm::ELF::ELFCLASS64; }

	llvm::MemoryBuffer* GetMemoryBuffer() override { return wrapper_.buffer.get(); }

	std::vector<ElfSegment> GetProgramHeader() override {
	auto program_headers = GetELFProgramHeaders(elf_);
	if (!program_headers) {
	return {};
	}
	std::vector<ElfSegment> segments(program_headers.get().size());
	for (size_t i = 0; i < program_headers.get().size(); i++) {
	const auto& phdr = program_headers.get()[i];
	segments[i].vaddr = phdr.p_vaddr;
	segments[i].file_offset = phdr.p_offset;
	segments[i].file_size = phdr.p_filesz;
	segments[i].is_executable =
	(phdr.p_type == llvm::ELF::PT_LOAD) && (phdr.p_flags & llvm::ELF::PF_X);
	segments[i].is_load = (phdr.p_type == llvm::ELF::PT_LOAD);
	}
	return segments;
	}

	std::vector<ElfSection> GetSectionHeader() override {
	auto section_headers_or_err = elf_->sections();
	if (!section_headers_or_err) {
	return {};
	}
	const auto& section_headers = section_headers_or_err.get();
	std::vector<ElfSection> sections(section_headers.size());
	for (size_t i = 0; i < section_headers.size(); i++) {
	const auto& shdr = section_headers[i];
	if (auto name = GetELFSectionName(elf_, shdr); name) {
	sections[i].name = name.get();
	}
	sections[i].vaddr = shdr.sh_addr;
	sections[i].file_offset = shdr.sh_offset;
	sections[i].size = shdr.sh_size;
	}
	return sections;
	}

	ElfStatus GetBuildId(BuildId* build_id) override {
	llvm::StringRef data = elf_obj_->getData();
	const char* binary_start = data.data();
	const char* binary_end = data.data() + data.size();
	for (auto it = elf_obj_->section_begin(); it != elf_obj_->section_end(); ++it) {
	const llvm::object::ELFSectionRef& section_ref = *it;
	if (section_ref.getType() == llvm::ELF::SHT_NOTE) {
	llvm::Expected<llvm::StringRef> content = GetSectionContents(section_ref);
	if (!content) {
	return ElfStatus::NO_BUILD_ID;
	}
	const llvm::StringRef& data = content.get();
	if (data.data() < binary_start \|\| data.data() + data.size() > binary_end) {
	return ElfStatus::NO_BUILD_ID;
	}
	if (GetBuildIdFromNoteSection(data.data(), data.size(), build_id)) {
	return ElfStatus::NO_ERROR;
	}
	}
	}
	return ElfStatus::NO_BUILD_ID;
	}

	ElfStatus ParseSymbols(const ParseSymbolCallback& callback) override {
	auto machine = GetELFHeader(elf_).e_machine;
	bool is_arm = (machine == llvm::ELF::EM_ARM \|\| machine == llvm::ELF::EM_AARCH64);
	AddSymbolForPltSection(elf_obj_, callback);
	// Some applications deliberately ship elf files with broken section tables.
	// So check the existence of .symtab section and .dynsym section before reading symbols.
	bool has_symtab;
	bool has_dynsym;
	CheckSymbolSections(elf_obj_, &has_symtab, &has_dynsym);
	if (has_symtab && elf_obj_->symbol_begin() != elf_obj_->symbol_end()) {
	ReadSymbolTable(elf_obj_->symbol_begin(), elf_obj_->symbol_end(), callback, is_arm,
	elf_obj_->section_end());
	return ElfStatus::NO_ERROR;
	} else if (has_dynsym && elf_obj_->dynamic_symbol_begin()->getRawDataRefImpl() !=
	llvm::object::DataRefImpl()) {
	ReadSymbolTable(elf_obj_->dynamic_symbol_begin(), elf_obj_->dynamic_symbol_end(), callback,
	is_arm, elf_obj_->section_end());
	}
	std::string debugdata;
	ElfStatus result = ReadSection(".gnu_debugdata", &debugdata);
	if (result == ElfStatus::SECTION_NOT_FOUND) {
	return ElfStatus::NO_SYMBOL_TABLE;
	} else if (result == ElfStatus::NO_ERROR) {
	std::string decompressed_data;
	if (XzDecompress(debugdata, &decompressed_data)) {
	auto debugdata_elf =
	ElfFile::Open(decompressed_data.data(), decompressed_data.size(), &result);
	if (debugdata_elf) {
	return debugdata_elf->ParseSymbols(callback);
	}
	}
	}
	return result;
	}

	void ParseDynamicSymbols(const ParseSymbolCallback& callback) override {
	auto machine = GetELFHeader(elf_).e_machine;
	bool is_arm = (machine == llvm::ELF::EM_ARM \|\| machine == llvm::ELF::EM_AARCH64);
	ReadSymbolTable(elf_obj_->dynamic_symbol_begin(), elf_obj_->dynamic_symbol_end(), callback,
	is_arm, elf_obj_->section_end());
	}

	ElfStatus ReadSection(const std::string& section_name, std::string* content) override {
	for (llvm::object::section_iterator it = elf_obj_->section_begin();
	it != elf_obj_->section_end(); ++it) {
	llvm::Expected<llvm::StringRef> name = GetSectionName(*it);
	if (!name \|\| name.get() != section_name) {
	continue;
	}
	llvm::Expected<llvm::StringRef> data = GetSectionContents(*it);
	if (!data) {
	return ElfStatus::READ_FAILED;
	}
	*content = data.get();
	return ElfStatus::NO_ERROR;
	}
	return ElfStatus::SECTION_NOT_FOUND;
	}

	uint64_t ReadMinExecutableVaddr(uint64_t* file_offset) {
	bool has_vaddr = false;
	uint64_t min_addr = std::numeric_limits<uint64_t>::max();
	auto program_headers = GetELFProgramHeaders(elf_);
	if (program_headers) {
	for (const auto& ph : program_headers.get()) {
	if ((ph.p_type == llvm::ELF::PT_LOAD) && (ph.p_flags & llvm::ELF::PF_X) &&
	(ph.p_vaddr < min_addr)) {
	min_addr = ph.p_vaddr;
	*file_offset = ph.p_offset;
	has_vaddr = true;
	}
	}
	}
	if (!has_vaddr) {
	// JIT symfiles don't have program headers.
	min_addr = 0;
	*file_offset = 0;
	}
	return min_addr;
	}

	bool VaddrToOff(uint64_t vaddr, uint64_t* file_offset) override {
	auto program_headers = GetELFProgramHeaders(elf_);
	if (!program_headers) {
	return false;
	}
	for (const auto& ph : program_headers.get()) {
	if (ph.p_type == llvm::ELF::PT_LOAD && vaddr >= ph.p_vaddr &&
	vaddr < ph.p_vaddr + ph.p_filesz) {
	*file_offset = vaddr - ph.p_vaddr + ph.p_offset;
	return true;
	}
	}
	return false;
	}

	private:
	BinaryWrapper wrapper_;
	const llvm::object::ELFObjectFile<ELFT>* elf_obj_;
	const llvm::object::ELFFile<ELFT>* elf_;
	};

	std::unique_ptr<ElfFile> CreateElfFileImpl(BinaryWrapper&& wrapper, ElfStatus* status) {
	if (auto obj = llvm::dyn_cast<llvm::object::ELF32LEObjectFile>(wrapper.obj.get())) {
	return std::unique_ptr<ElfFile>(
	new ElfFileImpl<llvm::object::ELF32LEObjectFile>(std::move(wrapper), obj));
	}
	if (auto obj = llvm::dyn_cast<llvm::object::ELF64LEObjectFile>(wrapper.obj.get())) {
	return std::unique_ptr<ElfFile>(
	new ElfFileImpl<llvm::object::ELF64LEObjectFile>(std::move(wrapper), obj));
	}
	*status = ElfStatus::FILE_MALFORMED;
	return nullptr;
	}

	} // namespace

	std::unique_ptr<ElfFile> ElfFile::Open(const std::string& filename) {
	ElfStatus status;
	auto elf = Open(filename, &status);
	if (!elf) {
	LOG(ERROR) << "failed to open " << filename << ": " << status;
	}
	return elf;
	}

	std::unique_ptr<ElfFile> ElfFile::Open(const std::string& filename,
	const BuildId* expected_build_id, ElfStatus* status) {
	BinaryWrapper wrapper;
	auto tuple = SplitUrlInApk(filename);
	if (std::get<0>(tuple)) {
	EmbeddedElf* elf = ApkInspector::FindElfInApkByName(std::get<1>(tuple), std::get<2>(tuple));
	if (elf == nullptr) {
	*status = ElfStatus::FILE_NOT_FOUND;
	} else {
	*status = OpenObjectFile(elf->filepath(), elf->entry_offset(), elf->entry_size(), &wrapper);
	}
	} else if (JITDebugReader::IsPathInJITSymFile(filename)) {
	size_t colon_pos = filename.rfind(':');
	CHECK_NE(colon_pos, std::string::npos);
	// path generated by JITDebugReader: app_jit_cache:<file_start>-<file_end>
	uint64_t file_start;
	uint64_t file_end;
	if (sscanf(filename.data() + colon_pos, ":%" PRIu64 "-%" PRIu64, &file_start, &file_end) != 2) {
	*status = ElfStatus::FILE_NOT_FOUND;
	return nullptr;
	}
	*status =
	OpenObjectFile(filename.substr(0, colon_pos), file_start, file_end - file_start, &wrapper);
	} else {
	*status = OpenObjectFile(filename, 0, 0, &wrapper);
	}
	if (*status != ElfStatus::NO_ERROR) {
	return nullptr;
	}
	auto elf = CreateElfFileImpl(std::move(wrapper), status);
	if (elf && expected_build_id != nullptr && !expected_build_id->IsEmpty()) {
	BuildId real_build_id;
	*status = elf->GetBuildId(&real_build_id);
	if (*status != ElfStatus::NO_ERROR) {
	return nullptr;
	}
	if (*expected_build_id != real_build_id) {
	*status = ElfStatus::BUILD_ID_MISMATCH;
	return nullptr;
	}
	}
	return elf;
	}

	std::unique_ptr<ElfFile> ElfFile::Open(const char* data, size_t size, ElfStatus* status) {
	BinaryWrapper wrapper;
	*status = OpenObjectFileInMemory(data, size, &wrapper);
	if (*status != ElfStatus::NO_ERROR) {
	return nullptr;
	}
	return CreateElfFileImpl(std::move(wrapper), status);
	}

	} // namespace simpleperf

	// LLVM libraries uses ncurses library, but that isn't needed by simpleperf.
	// So support a naive implementation to avoid depending on ncurses.
	__attribute__((weak)) extern "C" int setupterm(char, int, int) {
	return -1;
	}

	__attribute__((weak)) extern "C" struct term* set_curterm(struct term*) {
	return nullptr;
	}

	__attribute__((weak)) extern "C" int del_curterm(struct term*) {
	return -1;
	}

	__attribute__((weak)) extern "C" int tigetnum(char*) {
	return -1;
	}