EGL Multifile Blobcache: Fix applyLRU
This CL contains updates our cache eviction to be an actual
LRU instead of random.
* Entries are now tracked in a sorted map such that old entries
are accessed first in applyLRU.
* Access and update times are tracked with nanosecond accuracy.
Additional tests:
* CacheEvictionIsLRU
Based on work by: Igor Nazarov <i.nazarov@samsung.com>
Test: libEGL_test, EGL_test, ANGLE trace tests, apps
Bug: b/351867582, b/380483358
Flag: com.android.graphics.egl.flags.multifile_blobcache_advanced_usage
Change-Id: I0b6f407b6d5a29f9487f7d7604d723e701c6f6d5
diff --git a/opengl/libs/EGL/MultifileBlobCache.cpp b/opengl/libs/EGL/MultifileBlobCache.cpp
index 917671d..53a08bb 100644
--- a/opengl/libs/EGL/MultifileBlobCache.cpp
+++ b/opengl/libs/EGL/MultifileBlobCache.cpp
@@ -47,6 +47,11 @@
constexpr uint32_t kMultifileMagic = 'MFB$';
constexpr uint32_t kCrcPlaceholder = 0;
+// When removing files, what fraction of the overall limit should be reached when removing files
+// A divisor of two will decrease the cache to 50%, four to 25% and so on
+// We use the same limit to manage size and entry count
+constexpr uint32_t kCacheLimitDivisor = 2;
+
namespace {
// Helper function to close entries or free them
@@ -76,6 +81,7 @@
mMaxTotalEntries(maxTotalEntries),
mTotalCacheSize(0),
mTotalCacheEntries(0),
+ mTotalCacheSizeDivisor(kCacheLimitDivisor),
mHotCacheLimit(0),
mHotCacheSize(0),
mWorkerThreadIdle(true) {
@@ -247,7 +253,8 @@
ALOGV("INIT: Entry %u is good, tracking it now.", entryHash);
// Track details for rapid lookup later and update total size
- trackEntry(entryHash, header.valueSize, fileSize, st.st_atime);
+ // Note access time is a full timespec instead of just seconds
+ trackEntry(entryHash, header.valueSize, fileSize, st.st_atim);
// Preload the entry for fast retrieval
if ((mHotCacheSize + fileSize) < mHotCacheLimit) {
@@ -357,7 +364,11 @@
std::string fullPath = mMultifileDirName + "/" + std::to_string(entryHash);
// Track the size and access time for quick recall and update the overall cache size
- trackEntry(entryHash, valueSize, fileSize, time(0));
+ struct timespec time = {0, 0};
+ if (flags::multifile_blobcache_advanced_usage()) {
+ clock_gettime(CLOCK_REALTIME, &time);
+ }
+ trackEntry(entryHash, valueSize, fileSize, time);
// Keep the entry in hot cache for quick retrieval
ALOGV("SET: Adding %u to hot cache.", entryHash);
@@ -439,6 +450,14 @@
if (mHotCache.find(entryHash) != mHotCache.end()) {
ALOGV("GET: HotCache HIT for entry %u", entryHash);
cacheEntry = mHotCache[entryHash].entryBuffer;
+
+ if (flags::multifile_blobcache_advanced_usage()) {
+ // Update last access time on disk
+ struct timespec times[2];
+ times[0].tv_nsec = UTIME_NOW;
+ times[1].tv_nsec = UTIME_OMIT;
+ utimensat(0, fullPath.c_str(), times, 0);
+ }
} else {
ALOGV("GET: HotCache MISS for entry: %u", entryHash);
@@ -467,6 +486,14 @@
cacheEntry =
reinterpret_cast<uint8_t*>(mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE, fd, 0));
+ if (flags::multifile_blobcache_advanced_usage()) {
+ // Update last access time and omit last modify time
+ struct timespec times[2];
+ times[0].tv_nsec = UTIME_NOW;
+ times[1].tv_nsec = UTIME_OMIT;
+ futimens(fd, times);
+ }
+
// We can close the file now and the mmap will remain
close(fd);
@@ -503,6 +530,13 @@
return 0;
}
+ if (flags::multifile_blobcache_advanced_usage()) {
+ // Update the entry time for this hash, so it reflects LRU
+ struct timespec time;
+ clock_gettime(CLOCK_REALTIME, &time);
+ updateEntryTime(entryHash, time);
+ }
+
// Remaining entry following the key is the value
uint8_t* cachedValue = cacheEntry + (keySize + sizeof(MultifileHeader));
memcpy(value, cachedValue, cachedValueSize);
@@ -638,9 +672,20 @@
}
void MultifileBlobCache::trackEntry(uint32_t entryHash, EGLsizeiANDROID valueSize, size_t fileSize,
- time_t accessTime) {
+ const timespec& accessTime) {
+#if COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
+ // When we add this entry to the map, it is sorted by accessTime
+ MultifileEntryStatsMapIter entryStatsIter =
+ mEntryStats.emplace(std::piecewise_construct, std::forward_as_tuple(accessTime),
+ std::forward_as_tuple(entryHash, valueSize, fileSize));
+
+ // Track all entries with quick access to its stats
+ mEntries.emplace(entryHash, entryStatsIter);
+#else
+ (void)accessTime;
mEntries.insert(entryHash);
- mEntryStats[entryHash] = {valueSize, fileSize, accessTime};
+ mEntryStats[entryHash] = {entryHash, valueSize, fileSize};
+#endif // COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
increaseTotalCacheSize(fileSize);
}
@@ -651,12 +696,18 @@
return false;
}
+#if COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
+ MultifileEntryStatsMapIter entryStatsIter = entryIter->second;
+ MultifileEntryStats entryStats = entryStatsIter->second;
+ decreaseTotalCacheSize(entryStats.fileSize);
+#else
auto entryStatsIter = mEntryStats.find(entryHash);
if (entryStatsIter == mEntryStats.end()) {
ALOGE("Failed to remove entryHash (%u) from mEntryStats", entryHash);
return false;
}
decreaseTotalCacheSize(entryStatsIter->second.fileSize);
+#endif // COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
mEntryStats.erase(entryStatsIter);
mEntries.erase(entryIter);
@@ -669,7 +720,40 @@
}
MultifileEntryStats MultifileBlobCache::getEntryStats(uint32_t entryHash) {
+#if COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
+ auto entryIter = mEntries.find(entryHash);
+ if (entryIter == mEntries.end()) {
+ return {};
+ }
+
+ MultifileEntryStatsMapIter entryStatsIter = entryIter->second;
+ MultifileEntryStats entryStats = entryStatsIter->second;
+ return entryStats;
+#else
return mEntryStats[entryHash];
+#endif // COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
+}
+
+void MultifileBlobCache::updateEntryTime(uint32_t entryHash, const timespec& newTime) {
+#if COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
+ // This function updates the ordering of the map by removing the old iterators
+ // and re-adding them. If should be perforant as it does not perform a full re-sort.
+ // First, pull out the old entryStats
+ auto entryIter = mEntries.find(entryHash);
+ MultifileEntryStatsMapIter entryStatsIter = entryIter->second;
+ MultifileEntryStats entryStats = std::move(entryStatsIter->second);
+
+ // Remove the old iterators
+ mEntryStats.erase(entryStatsIter);
+ mEntries.erase(entryIter);
+
+ // Insert the new with updated time
+ entryStatsIter = mEntryStats.emplace(std::make_pair(newTime, std::move(entryStats)));
+ mEntries.emplace(entryHash, entryStatsIter);
+#else
+ (void)entryHash;
+ (void)newTime;
+#endif // COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
}
void MultifileBlobCache::increaseTotalCacheSize(size_t fileSize) {
@@ -751,8 +835,13 @@
bool MultifileBlobCache::applyLRU(size_t cacheSizeLimit, size_t cacheEntryLimit) {
// Walk through our map of sorted last access times and remove files until under the limit
for (auto cacheEntryIter = mEntryStats.begin(); cacheEntryIter != mEntryStats.end();) {
+#if COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
+ const MultifileEntryStats& entryStats = cacheEntryIter->second;
+ uint32_t entryHash = entryStats.entryHash;
+#else
uint32_t entryHash = cacheEntryIter->first;
const MultifileEntryStats& entryStats = cacheEntryIter->second;
+#endif // COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
ALOGV("LRU: Removing entryHash %u", entryHash);
@@ -823,11 +912,6 @@
return true;
}
-// When removing files, what fraction of the overall limit should be reached when removing files
-// A divisor of two will decrease the cache to 50%, four to 25% and so on
-// We use the same limit to manage size and entry count
-constexpr uint32_t kCacheLimitDivisor = 2;
-
// Calculate the cache size and remove old entries until under the limit
void MultifileBlobCache::trimCache() {
// Wait for all deferred writes to complete
@@ -835,8 +919,10 @@
waitForWorkComplete();
ALOGV("TRIM: Reducing multifile cache size to %zu, entries %zu",
- mMaxTotalSize / kCacheLimitDivisor, mMaxTotalEntries / kCacheLimitDivisor);
- if (!applyLRU(mMaxTotalSize / kCacheLimitDivisor, mMaxTotalEntries / kCacheLimitDivisor)) {
+ mMaxTotalSize / mTotalCacheSizeDivisor, mMaxTotalEntries / mTotalCacheSizeDivisor);
+
+ if (!applyLRU(mMaxTotalSize / mTotalCacheSizeDivisor,
+ mMaxTotalEntries / mTotalCacheSizeDivisor)) {
ALOGE("Error when clearing multifile shader cache");
return;
}
@@ -878,6 +964,14 @@
return;
}
+ if (flags::multifile_blobcache_advanced_usage()) {
+ // Update last access time and last modify time
+ struct timespec times[2];
+ times[0].tv_nsec = UTIME_NOW;
+ times[1].tv_nsec = UTIME_NOW;
+ futimens(fd, times);
+ }
+
ALOGV("DEFERRED: Completed write for: %s", fullPath.c_str());
close(fd);
diff --git a/opengl/libs/EGL/MultifileBlobCache.h b/opengl/libs/EGL/MultifileBlobCache.h
index fe477bc..3bd393f 100644
--- a/opengl/libs/EGL/MultifileBlobCache.h
+++ b/opengl/libs/EGL/MultifileBlobCache.h
@@ -49,9 +49,9 @@
};
struct MultifileEntryStats {
+ uint32_t entryHash;
EGLsizeiANDROID valueSize;
size_t fileSize;
- time_t accessTime;
};
struct MultifileStatus {
@@ -104,6 +104,26 @@
size_t mBufferSize;
};
+#if COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
+struct MultifileTimeLess {
+ bool operator()(const struct timespec& t1, const struct timespec& t2) const {
+ if (t1.tv_sec == t2.tv_sec) {
+ // If seconds are equal, check nanoseconds
+ return t1.tv_nsec < t2.tv_nsec;
+ } else {
+ // Otherwise, compare seconds
+ return t1.tv_sec < t2.tv_sec;
+ }
+ }
+};
+
+// The third parameter here causes all entries to be sorted by access time,
+// so oldest will be accessed first in applyLRU
+using MultifileEntryStatsMap =
+ std::multimap<struct timespec, MultifileEntryStats, MultifileTimeLess>;
+using MultifileEntryStatsMapIter = MultifileEntryStatsMap::iterator;
+#endif // COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
+
class MultifileBlobCache {
public:
MultifileBlobCache(size_t maxKeySize, size_t maxValueSize, size_t maxTotalSize,
@@ -119,6 +139,7 @@
size_t getTotalSize() const { return mTotalCacheSize; }
size_t getTotalEntries() const { return mTotalCacheEntries; }
+ size_t getTotalCacheSizeDivisor() const { return mTotalCacheSizeDivisor; }
const std::string& getCurrentBuildId() const { return mBuildId; }
void setCurrentBuildId(const std::string& buildId) { mBuildId = buildId; }
@@ -128,10 +149,11 @@
private:
void trackEntry(uint32_t entryHash, EGLsizeiANDROID valueSize, size_t fileSize,
- time_t accessTime);
+ const timespec& accessTime);
bool contains(uint32_t entryHash) const;
bool removeEntry(uint32_t entryHash);
MultifileEntryStats getEntryStats(uint32_t entryHash);
+ void updateEntryTime(uint32_t entryHash, const timespec& newTime);
bool createStatus(const std::string& baseDir);
bool checkStatus(const std::string& baseDir);
@@ -155,8 +177,14 @@
std::string mBuildId;
uint32_t mCacheVersion;
+#if COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
+ std::unordered_map<uint32_t, MultifileEntryStatsMapIter> mEntries;
+ MultifileEntryStatsMap mEntryStats;
+#else
std::unordered_set<uint32_t> mEntries;
std::unordered_map<uint32_t, MultifileEntryStats> mEntryStats;
+#endif // COM_ANDROID_GRAPHICS_EGL_FLAGS(MULTIFILE_BLOBCACHE_ADVANCED_USAGE)
+
std::unordered_map<uint32_t, MultifileHotCache> mHotCache;
size_t mMaxKeySize;
@@ -165,6 +193,7 @@
size_t mMaxTotalEntries;
size_t mTotalCacheSize;
size_t mTotalCacheEntries;
+ size_t mTotalCacheSizeDivisor;
size_t mHotCacheLimit;
size_t mHotCacheEntryLimit;
size_t mHotCacheSize;
diff --git a/opengl/libs/EGL/MultifileBlobCache_test.cpp b/opengl/libs/EGL/MultifileBlobCache_test.cpp
index c95bf28..74352d4 100644
--- a/opengl/libs/EGL/MultifileBlobCache_test.cpp
+++ b/opengl/libs/EGL/MultifileBlobCache_test.cpp
@@ -318,7 +318,7 @@
struct stat info;
if (stat(multifileDirName.c_str(), &info) == 0) {
- // We have a multifile dir. Skip the status file and return the only entry.
+ // We have a multifile dir. Skip the status file and return the entries.
DIR* dir;
struct dirent* entry;
if ((dir = opendir(multifileDirName.c_str())) != nullptr) {
@@ -329,6 +329,7 @@
if (strcmp(entry->d_name, kMultifileBlobCacheStatusFile) == 0) {
continue;
}
+ // printf("Found entry: %s\n", entry->d_name);
cacheEntries.push_back(multifileDirName + "/" + entry->d_name);
}
} else {
@@ -607,4 +608,123 @@
}
}
+// Ensure cache eviction is LRU
+TEST_F(MultifileBlobCacheTest, CacheEvictionIsLRU) {
+ if (!flags::multifile_blobcache_advanced_usage()) {
+ GTEST_SKIP() << "Skipping test that requires multifile_blobcache_advanced_usage flag";
+ }
+
+ // Fill the cache with exactly how much it can hold
+ int entry = 0;
+ for (entry = 0; entry < kMaxTotalEntries; entry++) {
+ // Use the index as the key and value
+ mMBC->set(&entry, sizeof(entry), &entry, sizeof(entry));
+
+ int result = 0;
+ ASSERT_EQ(sizeof(entry), mMBC->get(&entry, sizeof(entry), &result, sizeof(result)));
+ ASSERT_EQ(entry, result);
+ }
+
+ // Ensure the cache is full
+ ASSERT_EQ(mMBC->getTotalEntries(), kMaxTotalEntries);
+
+ // Add one more entry to trigger eviction
+ size_t overflowEntry = kMaxTotalEntries;
+ mMBC->set(&overflowEntry, sizeof(overflowEntry), &overflowEntry, sizeof(overflowEntry));
+
+ // Verify it contains the right amount, which will be one more than reduced size
+ // because we evict the cache before adding a new entry
+ size_t evictionLimit = kMaxTotalEntries / mMBC->getTotalCacheSizeDivisor();
+ ASSERT_EQ(mMBC->getTotalEntries(), evictionLimit + 1);
+
+ // Ensure cache is as expected, with old entries removed, newer entries remaining
+ for (entry = 0; entry < kMaxTotalEntries; entry++) {
+ int result = 0;
+ mMBC->get(&entry, sizeof(entry), &result, sizeof(result));
+
+ if (entry < evictionLimit) {
+ // We should get no hits on evicted entries, i.e. the first added
+ ASSERT_EQ(result, 0);
+ } else {
+ // Above the limit should still be present
+ ASSERT_EQ(result, entry);
+ }
+ }
+}
+
+// Ensure calling GET on an entry updates its access time, even if already in hotcache
+TEST_F(MultifileBlobCacheTest, GetUpdatesAccessTime) {
+ if (!flags::multifile_blobcache_advanced_usage()) {
+ GTEST_SKIP() << "Skipping test that requires multifile_blobcache_advanced_usage flag";
+ }
+
+ // Fill the cache with exactly how much it can hold
+ int entry = 0;
+ int result = 0;
+ for (entry = 0; entry < kMaxTotalEntries; entry++) {
+ // Use the index as the key and value
+ mMBC->set(&entry, sizeof(entry), &entry, sizeof(entry));
+ ASSERT_EQ(sizeof(entry), mMBC->get(&entry, sizeof(entry), &result, sizeof(result)));
+ ASSERT_EQ(entry, result);
+ }
+
+ // Ensure the cache is full
+ ASSERT_EQ(mMBC->getTotalEntries(), kMaxTotalEntries);
+
+ // GET the first few entries to update their access time
+ std::vector<int> accessedEntries = {1, 2, 3};
+ for (int i = 0; i < accessedEntries.size(); i++) {
+ entry = accessedEntries[i];
+ ASSERT_EQ(sizeof(entry), mMBC->get(&entry, sizeof(entry), &result, sizeof(result)));
+ }
+
+ // Add one more entry to trigger eviction
+ size_t overflowEntry = kMaxTotalEntries;
+ mMBC->set(&overflowEntry, sizeof(overflowEntry), &overflowEntry, sizeof(overflowEntry));
+
+ size_t evictionLimit = kMaxTotalEntries / mMBC->getTotalCacheSizeDivisor();
+
+ // Ensure cache is as expected, with old entries removed, newer entries remaining
+ for (entry = 0; entry < kMaxTotalEntries; entry++) {
+ int result = 0;
+ mMBC->get(&entry, sizeof(entry), &result, sizeof(result));
+
+ if (std::find(accessedEntries.begin(), accessedEntries.end(), entry) !=
+ accessedEntries.end()) {
+ // If this is one of the handful we accessed after filling the cache,
+ // they should still be in the cache because LRU
+ ASSERT_EQ(result, entry);
+ } else if (entry >= (evictionLimit + accessedEntries.size())) {
+ // If they were above the eviction limit (plus three for our updated entries),
+ // they should still be present
+ ASSERT_EQ(result, entry);
+ } else {
+ // Otherwise, they shold be evicted and no longer present
+ ASSERT_EQ(result, 0);
+ }
+ }
+
+ // Close the cache so everything writes out
+ mMBC->finish();
+ mMBC.reset();
+
+ // Open the cache again
+ mMBC.reset(new MultifileBlobCache(kMaxKeySize, kMaxValueSize, kMaxTotalSize, kMaxTotalEntries,
+ &mTempFile->path[0]));
+
+ // Check the cache again, ensuring the updated access time made it to disk
+ for (entry = 0; entry < kMaxTotalEntries; entry++) {
+ int result = 0;
+ mMBC->get(&entry, sizeof(entry), &result, sizeof(result));
+ if (std::find(accessedEntries.begin(), accessedEntries.end(), entry) !=
+ accessedEntries.end()) {
+ ASSERT_EQ(result, entry);
+ } else if (entry >= (evictionLimit + accessedEntries.size())) {
+ ASSERT_EQ(result, entry);
+ } else {
+ ASSERT_EQ(result, 0);
+ }
+ }
+}
+
} // namespace android