Add support for caching small reads.
Add benchmarking to verify this is faster.
Test: Ran unit tests.
Change-Id: I1487114331f4581ec2368e56c4f18c6e3e6bcc7d
diff --git a/libunwindstack/Android.bp b/libunwindstack/Android.bp
index 14f82c7..a5e0dc9 100644
--- a/libunwindstack/Android.bp
+++ b/libunwindstack/Android.bp
@@ -184,6 +184,7 @@
"tests/MapInfoGetLoadBiasTest.cpp",
"tests/MapsTest.cpp",
"tests/MemoryBufferTest.cpp",
+ "tests/MemoryCacheTest.cpp",
"tests/MemoryFake.cpp",
"tests/MemoryFileTest.cpp",
"tests/MemoryLocalTest.cpp",
@@ -310,6 +311,28 @@
],
}
+//-------------------------------------------------------------------------
+// Benchmarks
+//-------------------------------------------------------------------------
+cc_benchmark {
+ name: "unwind_benchmarks",
+ host_supported: true,
+ defaults: ["libunwindstack_flags"],
+
+ // Disable optimizations so that all of the calls are not optimized away.
+ cflags: [
+ "-O0",
+ ],
+
+ srcs: [
+ "benchmarks/unwind_benchmarks.cpp",
+ ],
+
+ shared_libs: [
+ "libunwindstack",
+ ],
+}
+
// Generates the elf data for use in the tests for .gnu_debugdata frames.
// Once these files are generated, use the xz command to compress the data.
cc_binary_host {
diff --git a/libunwindstack/Memory.cpp b/libunwindstack/Memory.cpp
index cfa8c6d..a30d65e 100644
--- a/libunwindstack/Memory.cpp
+++ b/libunwindstack/Memory.cpp
@@ -174,6 +174,13 @@
return std::shared_ptr<Memory>(new MemoryRemote(pid));
}
+std::shared_ptr<Memory> Memory::CreateProcessMemoryCached(pid_t pid) {
+ if (pid == getpid()) {
+ return std::shared_ptr<Memory>(new MemoryCache(new MemoryLocal()));
+ }
+ return std::shared_ptr<Memory>(new MemoryCache(new MemoryRemote(pid)));
+}
+
size_t MemoryBuffer::Read(uint64_t addr, void* dst, size_t size) {
if (addr >= raw_.size()) {
return 0;
@@ -398,4 +405,50 @@
return 0;
}
+size_t MemoryCache::Read(uint64_t addr, void* dst, size_t size) {
+ // Only bother caching and looking at the cache if this is a small read for now.
+ if (size > 64) {
+ return impl_->Read(addr, dst, size);
+ }
+
+ uint64_t addr_page = addr >> kCacheBits;
+ auto entry = cache_.find(addr_page);
+ uint8_t* cache_dst;
+ if (entry != cache_.end()) {
+ cache_dst = entry->second;
+ } else {
+ cache_dst = cache_[addr_page];
+ if (!impl_->ReadFully(addr_page << kCacheBits, cache_dst, kCacheSize)) {
+ // Erase the entry.
+ cache_.erase(addr_page);
+ return impl_->Read(addr, dst, size);
+ }
+ }
+ size_t max_read = ((addr_page + 1) << kCacheBits) - addr;
+ if (size <= max_read) {
+ memcpy(dst, &cache_dst[addr & kCacheMask], size);
+ return size;
+ }
+
+ // The read crossed into another cached entry, since a read can only cross
+ // into one extra cached page, duplicate the code rather than looping.
+ memcpy(dst, &cache_dst[addr & kCacheMask], max_read);
+ dst = &reinterpret_cast<uint8_t*>(dst)[max_read];
+ addr_page++;
+
+ entry = cache_.find(addr_page);
+ if (entry != cache_.end()) {
+ cache_dst = entry->second;
+ } else {
+ cache_dst = cache_[addr_page];
+ if (!impl_->ReadFully(addr_page << kCacheBits, cache_dst, kCacheSize)) {
+ // Erase the entry.
+ cache_.erase(addr_page);
+ return impl_->Read(addr_page << kCacheBits, dst, size - max_read) + max_read;
+ }
+ }
+ memcpy(dst, cache_dst, size - max_read);
+ return size;
+}
+
} // namespace unwindstack
diff --git a/libunwindstack/benchmarks/unwind_benchmarks.cpp b/libunwindstack/benchmarks/unwind_benchmarks.cpp
new file mode 100644
index 0000000..db0fb54
--- /dev/null
+++ b/libunwindstack/benchmarks/unwind_benchmarks.cpp
@@ -0,0 +1,83 @@
+/*
+ * Copyright (C) 2018 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 <stdint.h>
+
+#include <memory>
+
+#include <benchmark/benchmark.h>
+
+#include <unwindstack/Maps.h>
+#include <unwindstack/Memory.h>
+#include <unwindstack/Regs.h>
+#include <unwindstack/RegsGetLocal.h>
+#include <unwindstack/Unwinder.h>
+
+size_t Call6(std::shared_ptr<unwindstack::Memory>& process_memory, unwindstack::Maps* maps) {
+ std::unique_ptr<unwindstack::Regs> regs(unwindstack::Regs::CreateFromLocal());
+ unwindstack::RegsGetLocal(regs.get());
+ unwindstack::Unwinder unwinder(32, maps, regs.get(), process_memory);
+ unwinder.Unwind();
+ return unwinder.NumFrames();
+}
+
+size_t Call5(std::shared_ptr<unwindstack::Memory>& process_memory, unwindstack::Maps* maps) {
+ return Call6(process_memory, maps);
+}
+
+size_t Call4(std::shared_ptr<unwindstack::Memory>& process_memory, unwindstack::Maps* maps) {
+ return Call5(process_memory, maps);
+}
+
+size_t Call3(std::shared_ptr<unwindstack::Memory>& process_memory, unwindstack::Maps* maps) {
+ return Call4(process_memory, maps);
+}
+
+size_t Call2(std::shared_ptr<unwindstack::Memory>& process_memory, unwindstack::Maps* maps) {
+ return Call3(process_memory, maps);
+}
+
+size_t Call1(std::shared_ptr<unwindstack::Memory>& process_memory, unwindstack::Maps* maps) {
+ return Call2(process_memory, maps);
+}
+
+static void BM_uncached_unwind(benchmark::State& state) {
+ auto process_memory = unwindstack::Memory::CreateProcessMemory(getpid());
+ unwindstack::LocalMaps maps;
+ if (!maps.Parse()) {
+ state.SkipWithError("Failed to parse local maps.");
+ }
+
+ for (auto _ : state) {
+ benchmark::DoNotOptimize(Call1(process_memory, &maps));
+ }
+}
+BENCHMARK(BM_uncached_unwind);
+
+static void BM_cached_unwind(benchmark::State& state) {
+ auto process_memory = unwindstack::Memory::CreateProcessMemoryCached(getpid());
+ unwindstack::LocalMaps maps;
+ if (!maps.Parse()) {
+ state.SkipWithError("Failed to parse local maps.");
+ }
+
+ for (auto _ : state) {
+ benchmark::DoNotOptimize(Call1(process_memory, &maps));
+ }
+}
+BENCHMARK(BM_cached_unwind);
+
+BENCHMARK_MAIN();
diff --git a/libunwindstack/include/unwindstack/Memory.h b/libunwindstack/include/unwindstack/Memory.h
index 9c425cb..dba41d1 100644
--- a/libunwindstack/include/unwindstack/Memory.h
+++ b/libunwindstack/include/unwindstack/Memory.h
@@ -25,6 +25,7 @@
#include <map>
#include <memory>
#include <string>
+#include <unordered_map>
#include <vector>
namespace unwindstack {
@@ -35,9 +36,12 @@
virtual ~Memory() = default;
static std::shared_ptr<Memory> CreateProcessMemory(pid_t pid);
+ static std::shared_ptr<Memory> CreateProcessMemoryCached(pid_t pid);
virtual bool ReadString(uint64_t addr, std::string* string, uint64_t max_read = UINT64_MAX);
+ virtual void Clear() {}
+
virtual size_t Read(uint64_t addr, void* dst, size_t size) = 0;
bool ReadFully(uint64_t addr, void* dst, size_t size);
@@ -51,6 +55,24 @@
}
};
+class MemoryCache : public Memory {
+ public:
+ MemoryCache(Memory* memory) : impl_(memory) {}
+ virtual ~MemoryCache() = default;
+
+ size_t Read(uint64_t addr, void* dst, size_t size) override;
+
+ void Clear() override { cache_.clear(); }
+
+ private:
+ constexpr static size_t kCacheBits = 12;
+ constexpr static size_t kCacheMask = (1 << kCacheBits) - 1;
+ constexpr static size_t kCacheSize = 1 << kCacheBits;
+ std::unordered_map<uint64_t, uint8_t[kCacheSize]> cache_;
+
+ std::unique_ptr<Memory> impl_;
+};
+
class MemoryBuffer : public Memory {
public:
MemoryBuffer() = default;
diff --git a/libunwindstack/tests/MemoryCacheTest.cpp b/libunwindstack/tests/MemoryCacheTest.cpp
new file mode 100644
index 0000000..a3def20
--- /dev/null
+++ b/libunwindstack/tests/MemoryCacheTest.cpp
@@ -0,0 +1,143 @@
+/*
+ * Copyright (C) 2018 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 <stdint.h>
+
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include <unwindstack/Memory.h>
+
+#include "MemoryFake.h"
+
+namespace unwindstack {
+
+class MemoryCacheTest : public ::testing::Test {
+ protected:
+ void SetUp() override {
+ memory_ = new MemoryFake;
+ memory_cache_.reset(new MemoryCache(memory_));
+
+ memory_->SetMemoryBlock(0x8000, 4096, 0xab);
+ memory_->SetMemoryBlock(0x9000, 4096, 0xde);
+ memory_->SetMemoryBlock(0xa000, 3000, 0x50);
+ }
+
+ MemoryFake* memory_;
+ std::unique_ptr<MemoryCache> memory_cache_;
+
+ constexpr static size_t kMaxCachedSize = 64;
+};
+
+TEST_F(MemoryCacheTest, cached_read) {
+ for (size_t i = 1; i <= kMaxCachedSize; i++) {
+ std::vector<uint8_t> buffer(i);
+ ASSERT_TRUE(memory_cache_->ReadFully(0x8000 + i, buffer.data(), i))
+ << "Read failed at size " << i;
+ ASSERT_EQ(std::vector<uint8_t>(i, 0xab), buffer) << "Failed at size " << i;
+ }
+
+ // Verify the cached data is used.
+ memory_->SetMemoryBlock(0x8000, 4096, 0xff);
+ for (size_t i = 1; i <= kMaxCachedSize; i++) {
+ std::vector<uint8_t> buffer(i);
+ ASSERT_TRUE(memory_cache_->ReadFully(0x8000 + i, buffer.data(), i))
+ << "Read failed at size " << i;
+ ASSERT_EQ(std::vector<uint8_t>(i, 0xab), buffer) << "Failed at size " << i;
+ }
+}
+
+TEST_F(MemoryCacheTest, no_cached_read_after_clear) {
+ for (size_t i = 1; i <= kMaxCachedSize; i++) {
+ std::vector<uint8_t> buffer(i);
+ ASSERT_TRUE(memory_cache_->ReadFully(0x8000 + i, buffer.data(), i))
+ << "Read failed at size " << i;
+ ASSERT_EQ(std::vector<uint8_t>(i, 0xab), buffer) << "Failed at size " << i;
+ }
+
+ // Verify the cached data is not used after a reset.
+ memory_cache_->Clear();
+ memory_->SetMemoryBlock(0x8000, 4096, 0xff);
+ for (size_t i = 1; i <= kMaxCachedSize; i++) {
+ std::vector<uint8_t> buffer(i);
+ ASSERT_TRUE(memory_cache_->ReadFully(0x8000 + i, buffer.data(), i))
+ << "Read failed at size " << i;
+ ASSERT_EQ(std::vector<uint8_t>(i, 0xff), buffer) << "Failed at size " << i;
+ }
+}
+
+TEST_F(MemoryCacheTest, cached_read_across_caches) {
+ std::vector<uint8_t> expect(16, 0xab);
+ expect.resize(32, 0xde);
+
+ std::vector<uint8_t> buffer(32);
+ ASSERT_TRUE(memory_cache_->ReadFully(0x8ff0, buffer.data(), 32));
+ ASSERT_EQ(expect, buffer);
+
+ // Verify the cached data is used.
+ memory_->SetMemoryBlock(0x8000, 4096, 0xff);
+ memory_->SetMemoryBlock(0x9000, 4096, 0xff);
+ ASSERT_TRUE(memory_cache_->ReadFully(0x8ff0, buffer.data(), 32));
+ ASSERT_EQ(expect, buffer);
+}
+
+TEST_F(MemoryCacheTest, no_cache_read) {
+ for (size_t i = kMaxCachedSize + 1; i < 2 * kMaxCachedSize; i++) {
+ std::vector<uint8_t> buffer(i);
+ ASSERT_TRUE(memory_cache_->ReadFully(0x8000 + i, buffer.data(), i))
+ << "Read failed at size " << i;
+ ASSERT_EQ(std::vector<uint8_t>(i, 0xab), buffer) << "Failed at size " << i;
+ }
+
+ // Verify the cached data is not used.
+ memory_->SetMemoryBlock(0x8000, 4096, 0xff);
+ for (size_t i = kMaxCachedSize + 1; i < 2 * kMaxCachedSize; i++) {
+ std::vector<uint8_t> buffer(i);
+ ASSERT_TRUE(memory_cache_->ReadFully(0x8000 + i, buffer.data(), i))
+ << "Read failed at size " << i;
+ ASSERT_EQ(std::vector<uint8_t>(i, 0xff), buffer) << "Failed at size " << i;
+ }
+}
+
+TEST_F(MemoryCacheTest, read_for_cache_fail) {
+ std::vector<uint8_t> buffer(kMaxCachedSize);
+ ASSERT_TRUE(memory_cache_->ReadFully(0xa010, buffer.data(), kMaxCachedSize));
+ ASSERT_EQ(std::vector<uint8_t>(kMaxCachedSize, 0x50), buffer);
+
+ // Verify the cached data is not used.
+ memory_->SetMemoryBlock(0xa000, 3000, 0xff);
+ ASSERT_TRUE(memory_cache_->ReadFully(0xa010, buffer.data(), kMaxCachedSize));
+ ASSERT_EQ(std::vector<uint8_t>(kMaxCachedSize, 0xff), buffer);
+}
+
+TEST_F(MemoryCacheTest, read_for_cache_fail_cross) {
+ std::vector<uint8_t> expect(16, 0xde);
+ expect.resize(32, 0x50);
+
+ std::vector<uint8_t> buffer(32);
+ ASSERT_TRUE(memory_cache_->ReadFully(0x9ff0, buffer.data(), 32));
+ ASSERT_EQ(expect, buffer);
+
+ // Verify the cached data is not used for the second half but for the first.
+ memory_->SetMemoryBlock(0xa000, 3000, 0xff);
+ ASSERT_TRUE(memory_cache_->ReadFully(0x9ff0, buffer.data(), 32));
+ expect.resize(16);
+ expect.resize(32, 0xff);
+ ASSERT_EQ(expect, buffer);
+}
+
+} // namespace unwindstack