diff options
author | David Srbecky <dsrbecky@google.com> | 2020-04-14 16:59:27 +0100 |
---|---|---|
committer | Christopher Ferris <cferris@google.com> | 2020-04-16 15:03:19 -0700 |
commit | a17c2b694ce53a484f534ba7abab7ec12cd4ffcc (patch) | |
tree | 9fbc74ee5582c15d71067201c46b7c5b3d554035 | |
parent | 8c6d5bf83c9551264932e8d4268870cc26567fed (diff) | |
download | core-a17c2b694ce53a484f534ba7abab7ec12cd4ffcc.tar.gz |
Optimize Memory::ReadString
This function is responsible for majority of CPU time in prefetto.
Reduce the number of memory reads (don't read strings byte-by-byte).
Update all calls of ReadString to include the third parameter to have
a max read.
Add an Elf creation benchmark since this function is on the elf
creation path.
Test: libunwindstack_unit_test
Change-Id: Ia36e1f1a5ba76c9e9f13c43fb9e3691dde7897f2
-rw-r--r-- | libunwindstack/Android.bp | 2 | ||||
-rw-r--r-- | libunwindstack/ElfInterface.cpp | 12 | ||||
-rw-r--r-- | libunwindstack/Memory.cpp | 34 | ||||
-rw-r--r-- | libunwindstack/benchmarks/ElfBenchmark.cpp | 77 | ||||
-rw-r--r-- | libunwindstack/benchmarks/SymbolBenchmark.cpp | 43 | ||||
-rw-r--r-- | libunwindstack/benchmarks/Utils.cpp | 62 | ||||
-rw-r--r-- | libunwindstack/benchmarks/Utils.h | 39 | ||||
-rw-r--r-- | libunwindstack/include/unwindstack/Memory.h | 2 | ||||
-rw-r--r-- | libunwindstack/tests/MemoryTest.cpp | 51 |
9 files changed, 263 insertions, 59 deletions
diff --git a/libunwindstack/Android.bp b/libunwindstack/Android.bp index ab59a4bab..21da12d45 100644 --- a/libunwindstack/Android.bp +++ b/libunwindstack/Android.bp @@ -373,7 +373,9 @@ cc_benchmark { srcs: [ "benchmarks/unwind_benchmarks.cpp", + "benchmarks/ElfBenchmark.cpp", "benchmarks/SymbolBenchmark.cpp", + "benchmarks/Utils.cpp", ], data: [ diff --git a/libunwindstack/ElfInterface.cpp b/libunwindstack/ElfInterface.cpp index 821e042b0..17470fd3e 100644 --- a/libunwindstack/ElfInterface.cpp +++ b/libunwindstack/ElfInterface.cpp @@ -371,7 +371,7 @@ void ElfInterface::ReadSectionHeaders(const EhdrType& ehdr) { // Look for the .debug_frame and .gnu_debugdata. if (shdr.sh_name < sec_size) { std::string name; - if (memory_->ReadString(sec_offset + shdr.sh_name, &name)) { + if (memory_->ReadString(sec_offset + shdr.sh_name, &name, sec_size - shdr.sh_name)) { if (name == ".debug_frame") { debug_frame_offset_ = shdr.sh_offset; debug_frame_size_ = shdr.sh_size; @@ -405,7 +405,7 @@ void ElfInterface::ReadSectionHeaders(const EhdrType& ehdr) { } else if (shdr.sh_type == SHT_NOTE) { if (shdr.sh_name < sec_size) { std::string name; - if (memory_->ReadString(sec_offset + shdr.sh_name, &name) && + if (memory_->ReadString(sec_offset + shdr.sh_name, &name, sec_size - shdr.sh_name) && name == ".note.gnu.build-id") { gnu_build_id_offset_ = shdr.sh_offset; gnu_build_id_size_ = shdr.sh_size; @@ -456,10 +456,11 @@ std::string ElfInterface::GetSonameWithTemplate() { for (const auto& entry : strtabs_) { if (entry.first == strtab_addr) { soname_offset = entry.second + soname_offset; - if (soname_offset >= entry.second + strtab_size) { + uint64_t soname_max = entry.second + strtab_size; + if (soname_offset >= soname_max) { return ""; } - if (!memory_->ReadString(soname_offset, &soname_)) { + if (!memory_->ReadString(soname_offset, &soname_, soname_max - soname_offset)) { return ""; } soname_type_ = SONAME_VALID; @@ -608,7 +609,8 @@ bool GetBuildIDInfo(Memory* memory, uint64_t* build_id_offset, uint64_t* build_i } std::string name; if (shdr.sh_type == SHT_NOTE && shdr.sh_name < sec_size && - memory->ReadString(sec_offset + shdr.sh_name, &name) && name == ".note.gnu.build-id") { + memory->ReadString(sec_offset + shdr.sh_name, &name, sec_size - shdr.sh_name) && + name == ".note.gnu.build-id") { *build_id_offset = shdr.sh_offset; *build_id_size = shdr.sh_size; return true; diff --git a/libunwindstack/Memory.cpp b/libunwindstack/Memory.cpp index 8de3d9808..e142b97df 100644 --- a/libunwindstack/Memory.cpp +++ b/libunwindstack/Memory.cpp @@ -158,20 +158,30 @@ bool Memory::ReadFully(uint64_t addr, void* dst, size_t size) { return rc == size; } -bool Memory::ReadString(uint64_t addr, std::string* string, uint64_t max_read) { - string->clear(); - uint64_t bytes_read = 0; - while (bytes_read < max_read) { - uint8_t value; - if (!ReadFully(addr, &value, sizeof(value))) { - return false; +bool Memory::ReadString(uint64_t addr, std::string* dst, size_t max_read) { + char buffer[256]; // Large enough for 99% of symbol names. + size_t size = 0; // Number of bytes which were read into the buffer. + for (size_t offset = 0; offset < max_read; offset += size) { + // Look for null-terminator first, so we can allocate string of exact size. + // If we know the end of valid memory range, do the reads in larger blocks. + size_t read = std::min(sizeof(buffer), max_read - offset); + size = Read(addr + offset, buffer, read); + if (size == 0) { + return false; // We have not found end of string yet and we can not read more data. } - if (value == '\0') { - return true; + size_t length = strnlen(buffer, size); // Index of the null-terminator. + if (length < size) { + // We found the null-terminator. Allocate the string and set its content. + if (offset == 0) { + // We did just single read, so the buffer already contains the whole string. + dst->assign(buffer, length); + return true; + } else { + // The buffer contains only the last block. Read the whole string again. + dst->assign(offset + length, '\0'); + return ReadFully(addr, dst->data(), dst->size()); + } } - string->push_back(value); - addr++; - bytes_read++; } return false; } diff --git a/libunwindstack/benchmarks/ElfBenchmark.cpp b/libunwindstack/benchmarks/ElfBenchmark.cpp new file mode 100644 index 000000000..c108a2aa7 --- /dev/null +++ b/libunwindstack/benchmarks/ElfBenchmark.cpp @@ -0,0 +1,77 @@ +/* + * Copyright (C) 2020 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 <err.h> +#include <malloc.h> +#include <stdint.h> + +#include <string> + +#include <benchmark/benchmark.h> + +#include <unwindstack/Elf.h> +#include <unwindstack/Memory.h> + +#include "Utils.h" + +static void BenchmarkElfCreate(benchmark::State& state, const std::string& elf_file) { +#if defined(__BIONIC__) + uint64_t rss_bytes = 0; +#endif + uint64_t alloc_bytes = 0; + for (auto _ : state) { + state.PauseTiming(); +#if defined(__BIONIC__) + mallopt(M_PURGE, 0); + uint64_t rss_bytes_before = 0; + GatherRss(&rss_bytes_before); +#endif + uint64_t alloc_bytes_before = mallinfo().uordblks; + auto file_memory = unwindstack::Memory::CreateFileMemory(elf_file, 0); + state.ResumeTiming(); + + unwindstack::Elf elf(file_memory.release()); + if (!elf.Init() || !elf.valid()) { + errx(1, "Internal Error: Cannot open elf."); + } + + state.PauseTiming(); +#if defined(__BIONIC__) + mallopt(M_PURGE, 0); +#endif + alloc_bytes += mallinfo().uordblks - alloc_bytes_before; +#if defined(__BIONIC__) + GatherRss(&rss_bytes); + rss_bytes -= rss_bytes_before; +#endif + state.ResumeTiming(); + } + +#if defined(__BIONIC__) + state.counters["RSS_BYTES"] = rss_bytes / static_cast<double>(state.iterations()); +#endif + state.counters["ALLOCATED_BYTES"] = alloc_bytes / static_cast<double>(state.iterations()); +} + +void BM_elf_create(benchmark::State& state) { + BenchmarkElfCreate(state, GetElfFile()); +} +BENCHMARK(BM_elf_create); + +void BM_elf_create_compressed(benchmark::State& state) { + BenchmarkElfCreate(state, GetCompressedElfFile()); +} +BENCHMARK(BM_elf_create_compressed); diff --git a/libunwindstack/benchmarks/SymbolBenchmark.cpp b/libunwindstack/benchmarks/SymbolBenchmark.cpp index a850ff047..73088dab0 100644 --- a/libunwindstack/benchmarks/SymbolBenchmark.cpp +++ b/libunwindstack/benchmarks/SymbolBenchmark.cpp @@ -22,33 +22,12 @@ #include <string> #include <vector> -#include <android-base/file.h> -#include <android-base/strings.h> #include <benchmark/benchmark.h> #include <unwindstack/Elf.h> #include <unwindstack/Memory.h> -#if defined(__BIONIC__) - -#include <meminfo/procmeminfo.h> -#include <procinfo/process_map.h> - -static void Gather(uint64_t* rss_bytes) { - android::meminfo::ProcMemInfo proc_mem(getpid()); - const std::vector<android::meminfo::Vma>& maps = proc_mem.MapsWithoutUsageStats(); - for (auto& vma : maps) { - if (vma.name == "[anon:libc_malloc]" || android::base::StartsWith(vma.name, "[anon:scudo:") || - android::base::StartsWith(vma.name, "[anon:GWP-ASan")) { - android::meminfo::Vma update_vma(vma); - if (!proc_mem.FillInVmaStats(update_vma)) { - err(1, "FillInVmaStats failed\n"); - } - *rss_bytes += update_vma.usage.rss; - } - } -} -#endif +#include "Utils.h" static void BenchmarkSymbolLookup(benchmark::State& state, std::vector<uint64_t> offsets, std::string elf_file, bool expect_found) { @@ -66,7 +45,7 @@ static void BenchmarkSymbolLookup(benchmark::State& state, std::vector<uint64_t> #if defined(__BIONIC__) mallopt(M_PURGE, 0); uint64_t rss_bytes_before = 0; - Gather(&rss_bytes_before); + GatherRss(&rss_bytes_before); #endif uint64_t alloc_bytes_before = mallinfo().uordblks; state.ResumeTiming(); @@ -88,7 +67,7 @@ static void BenchmarkSymbolLookup(benchmark::State& state, std::vector<uint64_t> #endif alloc_bytes += mallinfo().uordblks - alloc_bytes_before; #if defined(__BIONIC__) - Gather(&rss_bytes); + GatherRss(&rss_bytes); rss_bytes -= rss_bytes_before; #endif state.ResumeTiming(); @@ -105,14 +84,6 @@ static void BenchmarkSymbolLookup(benchmark::State& state, uint64_t pc, std::str BenchmarkSymbolLookup(state, std::vector<uint64_t>{pc}, elf_file, expect_found); } -std::string GetElfFile() { - return android::base::GetExecutableDirectory() + "/benchmarks/files/libart_arm.so"; -} - -std::string GetSortedElfFile() { - return android::base::GetExecutableDirectory() + "/benchmarks/files/boot_arm.oat"; -} - void BM_symbol_not_present(benchmark::State& state) { BenchmarkSymbolLookup(state, 0, GetElfFile(), false); } @@ -136,23 +107,23 @@ void BM_symbol_find_multiple(benchmark::State& state) { BENCHMARK(BM_symbol_find_multiple); void BM_symbol_not_present_from_sorted(benchmark::State& state) { - BenchmarkSymbolLookup(state, 0, GetSortedElfFile(), false); + BenchmarkSymbolLookup(state, 0, GetSymbolSortedElfFile(), false); } BENCHMARK(BM_symbol_not_present_from_sorted); void BM_symbol_find_single_from_sorted(benchmark::State& state) { - BenchmarkSymbolLookup(state, 0x138638, GetSortedElfFile(), true); + BenchmarkSymbolLookup(state, 0x138638, GetSymbolSortedElfFile(), true); } BENCHMARK(BM_symbol_find_single_from_sorted); void BM_symbol_find_single_many_times_from_sorted(benchmark::State& state) { - BenchmarkSymbolLookup(state, std::vector<uint64_t>(15, 0x138638), GetSortedElfFile(), true); + BenchmarkSymbolLookup(state, std::vector<uint64_t>(15, 0x138638), GetSymbolSortedElfFile(), true); } BENCHMARK(BM_symbol_find_single_many_times_from_sorted); void BM_symbol_find_multiple_from_sorted(benchmark::State& state) { BenchmarkSymbolLookup(state, std::vector<uint64_t>{0x138638, 0x84350, 0x14df18, 0x1f3a38, 0x1f3ca8}, - GetSortedElfFile(), true); + GetSymbolSortedElfFile(), true); } BENCHMARK(BM_symbol_find_multiple_from_sorted); diff --git a/libunwindstack/benchmarks/Utils.cpp b/libunwindstack/benchmarks/Utils.cpp new file mode 100644 index 000000000..c92f1099d --- /dev/null +++ b/libunwindstack/benchmarks/Utils.cpp @@ -0,0 +1,62 @@ +/* + * Copyright (C) 2020 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 <err.h> +#include <stdint.h> + +#include <string> +#include <vector> + +#include <android-base/file.h> +#include <android-base/strings.h> +#include <benchmark/benchmark.h> + +#include <unwindstack/Elf.h> +#include <unwindstack/Memory.h> + +std::string GetElfFile() { + return android::base::GetExecutableDirectory() + "/benchmarks/files/libart_arm.so"; +} + +std::string GetSymbolSortedElfFile() { + return android::base::GetExecutableDirectory() + "/benchmarks/files/boot_arm.oat"; +} + +std::string GetCompressedElfFile() { + // Both are the same right now. + return GetSymbolSortedElfFile(); +} + +#if defined(__BIONIC__) + +#include <meminfo/procmeminfo.h> +#include <procinfo/process_map.h> + +void GatherRss(uint64_t* rss_bytes) { + android::meminfo::ProcMemInfo proc_mem(getpid()); + const std::vector<android::meminfo::Vma>& maps = proc_mem.MapsWithoutUsageStats(); + for (auto& vma : maps) { + if (vma.name == "[anon:libc_malloc]" || android::base::StartsWith(vma.name, "[anon:scudo:") || + android::base::StartsWith(vma.name, "[anon:GWP-ASan")) { + android::meminfo::Vma update_vma(vma); + if (!proc_mem.FillInVmaStats(update_vma)) { + err(1, "FillInVmaStats failed\n"); + } + *rss_bytes += update_vma.usage.rss; + } + } +} +#endif diff --git a/libunwindstack/benchmarks/Utils.h b/libunwindstack/benchmarks/Utils.h new file mode 100644 index 000000000..bee6efcad --- /dev/null +++ b/libunwindstack/benchmarks/Utils.h @@ -0,0 +1,39 @@ +/* + * Copyright (C) 2020 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. + */ + +#ifndef _LIBUNWINDSTACK_UTILS_H +#define _LIBUNWINDSTACK_UTILS_H + +#include <stdint.h> + +#include <string> + +std::string GetElfFile(); + +std::string GetSymbolSortedElfFile(); + +std::string GetCompressedElfFile(); + +#if defined(__BIONIC__) + +#include <meminfo/procmeminfo.h> +#include <procinfo/process_map.h> + +void GatherRss(uint64_t* rss_bytes); + +#endif + +#endif // _LIBUNWINDSTACK_UTILS_h diff --git a/libunwindstack/include/unwindstack/Memory.h b/libunwindstack/include/unwindstack/Memory.h index ecd908a5d..995230e39 100644 --- a/libunwindstack/include/unwindstack/Memory.h +++ b/libunwindstack/include/unwindstack/Memory.h @@ -37,7 +37,7 @@ class Memory { uint64_t end); static std::unique_ptr<Memory> CreateFileMemory(const std::string& path, uint64_t offset); - virtual bool ReadString(uint64_t addr, std::string* string, uint64_t max_read = UINT64_MAX); + virtual bool ReadString(uint64_t addr, std::string* dst, size_t max_read); virtual void Clear() {} diff --git a/libunwindstack/tests/MemoryTest.cpp b/libunwindstack/tests/MemoryTest.cpp index 365598499..8a8eb24f5 100644 --- a/libunwindstack/tests/MemoryTest.cpp +++ b/libunwindstack/tests/MemoryTest.cpp @@ -59,10 +59,10 @@ TEST(MemoryTest, read_string) { memory.SetMemory(100, name.c_str(), name.size() + 1); std::string dst_name; - ASSERT_TRUE(memory.ReadString(100, &dst_name)); + ASSERT_TRUE(memory.ReadString(100, &dst_name, 100)); ASSERT_EQ("string_in_memory", dst_name); - ASSERT_TRUE(memory.ReadString(107, &dst_name)); + ASSERT_TRUE(memory.ReadString(107, &dst_name, 100)); ASSERT_EQ("in_memory", dst_name); // Set size greater than string. @@ -82,15 +82,56 @@ TEST(MemoryTest, read_string_error) { std::string dst_name; // Read from a non-existant address. - ASSERT_FALSE(memory.ReadString(100, &dst_name)); + ASSERT_FALSE(memory.ReadString(100, &dst_name, 100)); // This should fail because there is no terminating '\0'. - ASSERT_FALSE(memory.ReadString(0, &dst_name)); + ASSERT_FALSE(memory.ReadString(0, &dst_name, 100)); // This should pass because there is a terminating '\0'. memory.SetData8(name.size(), '\0'); - ASSERT_TRUE(memory.ReadString(0, &dst_name)); + ASSERT_TRUE(memory.ReadString(0, &dst_name, 100)); ASSERT_EQ("short", dst_name); } +TEST(MemoryTest, read_string_long) { + // This string should be greater than 768 characters long (greater than 3 times + // the buffer in the ReadString function) to read multiple blocks. + static constexpr char kLongString[] = + "one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen " + "sixteen seventeen eightteen nineteen twenty twenty-one twenty-two twenty-three twenty-four " + "twenty-five twenty-six twenty-seven twenty-eight twenty-nine thirty thirty-one thirty-two " + "thirty-three thirty-four thirty-five thirty-six thirty-seven thirty-eight thirty-nine forty " + "forty-one forty-two forty-three forty-four forty-five forty-size forty-seven forty-eight " + "forty-nine fifty fifty-one fifty-two fifty-three fifty-four fifty-five fifty-six " + "fifty-seven fifty-eight fifty-nine sixty sixty-one sixty-two sixty-three sixty-four " + "sixty-five sixty-six sixty-seven sixty-eight sixty-nine seventy seventy-one seventy-two " + "seventy-three seventy-four seventy-five seventy-six seventy-seven seventy-eight " + "seventy-nine eighty"; + + MemoryFake memory; + + memory.SetMemory(100, kLongString, sizeof(kLongString)); + + std::string dst_name; + ASSERT_TRUE(memory.ReadString(100, &dst_name, sizeof(kLongString))); + ASSERT_EQ(kLongString, dst_name); + + std::string expected_str(kLongString, 255); + memory.SetMemory(100, expected_str.data(), expected_str.length() + 1); + ASSERT_TRUE(memory.ReadString(100, &dst_name, 256)); + ASSERT_EQ(expected_str, dst_name); + ASSERT_FALSE(memory.ReadString(100, &dst_name, 255)); + + expected_str = std::string(kLongString, 256); + memory.SetMemory(100, expected_str.data(), expected_str.length() + 1); + ASSERT_TRUE(memory.ReadString(100, &dst_name, 257)); + ASSERT_EQ(expected_str, dst_name); + ASSERT_FALSE(memory.ReadString(100, &dst_name, 256)); + + expected_str = std::string(kLongString, 299); + memory.SetMemory(100, expected_str.data(), expected_str.length() + 1); + ASSERT_TRUE(memory.ReadString(100, &dst_name, 300)); + ASSERT_EQ(expected_str, dst_name); +} + } // namespace unwindstack |