Add LRU cache.
Change-Id: I0e6ac4dca8ece99d4f69d588a34b2d003da69bea
Bug: 73625480
diff --git a/Android.bp b/Android.bp
index aad645f..6c25b26 100644
--- a/Android.bp
+++ b/Android.bp
@@ -3124,6 +3124,8 @@
"src/protozero/test/protozero_conformance_unittest.cc",
"src/traced/probes/filesystem/fs_mount.cc",
"src/traced/probes/filesystem/fs_mount_unittest.cc",
+ "src/traced/probes/filesystem/lru_inode_cache.cc",
+ "src/traced/probes/filesystem/lru_inode_cache_unittest.cc",
"src/traced/probes/probes_producer.cc",
"src/traced/probes/process_stats_data_source.cc",
"src/traced/probes/process_stats_data_source_unittest.cc",
diff --git a/src/traced/probes/filesystem/BUILD.gn b/src/traced/probes/filesystem/BUILD.gn
index 71e3d79..40aebc7 100644
--- a/src/traced/probes/filesystem/BUILD.gn
+++ b/src/traced/probes/filesystem/BUILD.gn
@@ -19,6 +19,8 @@
sources = [
"fs_mount.cc",
"fs_mount.h",
+ "lru_inode_cache.cc",
+ "lru_inode_cache.h",
]
}
@@ -31,5 +33,6 @@
]
sources = [
"fs_mount_unittest.cc",
+ "lru_inode_cache_unittest.cc",
]
}
diff --git a/src/traced/probes/filesystem/lru_inode_cache.cc b/src/traced/probes/filesystem/lru_inode_cache.cc
new file mode 100644
index 0000000..ca9f30b
--- /dev/null
+++ b/src/traced/probes/filesystem/lru_inode_cache.cc
@@ -0,0 +1,60 @@
+/*
+ * 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 "src/traced/probes/filesystem/lru_inode_cache.h"
+
+namespace perfetto {
+namespace base {
+
+const LRUInodeCache::InodeValue* LRUInodeCache::Get(const InodeKey& k) {
+ const auto& map_it = map_.find(k);
+ if (map_it == map_.end()) {
+ return nullptr;
+ }
+ auto list_entry = map_it->second;
+ // Bump this item to the front of the cache.
+ // We can borrow both elements of the pair stored in the list because
+ // insert does not need them.
+ Insert(map_it, std::move(list_entry->first), std::move(list_entry->second));
+ return &list_.cbegin()->second;
+}
+
+void LRUInodeCache::Insert(InodeKey k, InodeValue v) {
+ auto it = map_.find(k);
+ return Insert(it, std::move(k), std::move(v));
+}
+
+void LRUInodeCache::Insert(typename MapType::iterator map_it,
+ InodeKey k,
+ InodeValue v) {
+ list_.emplace_front(k, std::move(v));
+ if (map_it != map_.end()) {
+ ListIteratorType& list_it = map_it->second;
+ list_.erase(list_it);
+ list_it = list_.begin();
+ } else {
+ map_.emplace(std::move(k), list_.begin());
+ }
+
+ if (map_.size() > capacity_) {
+ auto list_last_it = list_.end();
+ list_last_it--;
+ map_.erase(list_last_it->first);
+ list_.erase(list_last_it);
+ }
+}
+} // namespace base
+} // namespace perfetto
diff --git a/src/traced/probes/filesystem/lru_inode_cache.h b/src/traced/probes/filesystem/lru_inode_cache.h
new file mode 100644
index 0000000..762373d
--- /dev/null
+++ b/src/traced/probes/filesystem/lru_inode_cache.h
@@ -0,0 +1,56 @@
+/*
+ * 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.
+ */
+
+#ifndef SRC_TRACED_PROBES_FILESYSTEM_LRU_INODE_CACHE_H_
+#define SRC_TRACED_PROBES_FILESYSTEM_LRU_INODE_CACHE_H_
+
+#include <list>
+#include <map>
+#include <string>
+#include <tuple>
+
+namespace perfetto {
+namespace base {
+
+// LRUInodeCache keeps up to |capacity| entries in a mapping from InodeKey
+// to InodeValue. This is used to map <block device, inode> tuples to file
+// paths.
+class LRUInodeCache {
+ public:
+ using InodeKey = std::pair<int64_t, int64_t>;
+ using InodeValue = std::string;
+
+ explicit LRUInodeCache(size_t capacity) : capacity_(capacity) {}
+
+ const LRUInodeCache::InodeValue* Get(const InodeKey& k);
+ void Insert(InodeKey k, LRUInodeCache::InodeValue v);
+
+ private:
+ using ItemType = std::pair<const InodeKey, const InodeValue>;
+ using ListIteratorType = std::list<ItemType>::iterator;
+ using MapType = std::map<const InodeKey, ListIteratorType>;
+
+ void Insert(MapType::iterator map_it, InodeKey k, InodeValue v);
+
+ const size_t capacity_;
+ MapType map_;
+ std::list<ItemType> list_;
+};
+
+} // namespace base
+} // namespace perfetto
+
+#endif // SRC_TRACED_PROBES_FILESYSTEM_LRU_INODE_CACHE_H_
diff --git a/src/traced/probes/filesystem/lru_inode_cache_unittest.cc b/src/traced/probes/filesystem/lru_inode_cache_unittest.cc
new file mode 100644
index 0000000..b8d8d56
--- /dev/null
+++ b/src/traced/probes/filesystem/lru_inode_cache_unittest.cc
@@ -0,0 +1,67 @@
+/*
+ * 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 "src/traced/probes/filesystem/lru_inode_cache.h"
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+#include <string>
+#include <tuple>
+
+namespace perfetto {
+namespace base {
+namespace {
+
+using ::testing::Eq;
+using ::testing::IsNull;
+using ::testing::Pointee;
+
+const std::pair<int64_t, int64_t> key1{0, 0};
+const std::pair<int64_t, int64_t> key2{0, 1};
+const std::pair<int64_t, int64_t> key3{0, 2};
+
+const char val1[] = "foo";
+const char val2[] = "bar";
+const char val3[] = "baz";
+
+TEST(LRUInodeCacheTest, Basic) {
+ LRUInodeCache cache(2);
+ cache.Insert(key1, val1);
+ EXPECT_THAT(cache.Get(key1), Pointee(Eq(val1)));
+ cache.Insert(key2, val2);
+ EXPECT_THAT(cache.Get(key1), Pointee(Eq(val1)));
+ EXPECT_THAT(cache.Get(key2), Pointee(Eq(val2)));
+ cache.Insert(key1, val2);
+ EXPECT_THAT(cache.Get(key1), Pointee(Eq(val2)));
+}
+
+TEST(LRUInodeCacheTest, Overflow) {
+ LRUInodeCache cache(2);
+ cache.Insert(key1, val1);
+ cache.Insert(key2, val2);
+ EXPECT_THAT(cache.Get(key1), Pointee(Eq(val1)));
+ EXPECT_THAT(cache.Get(key2), Pointee(Eq(val2)));
+ cache.Insert(key3, val3);
+ // key1 is the LRU and should be evicted.
+ EXPECT_THAT(cache.Get(key1), IsNull());
+ EXPECT_THAT(cache.Get(key2), Pointee(Eq(val2)));
+ EXPECT_THAT(cache.Get(key3), Pointee(Eq(val3)));
+}
+
+} // namespace
+} // namespace base
+} // namespace perfetto