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

3 files changed, 257 insertions, 14 deletions

diff --git a/opengl/libs/EGL/MultifileBlobCache.cpp b/opengl/libs/EGL/MultifileBlobCache.cpp
index 917671d9ab..53a08bb59d 100644
--- a/opengl/libs/EGL/MultifileBlobCache.cpp
+++ b/opengl/libs/EGL/MultifileBlobCache.cpp
@@ -47,6 +47,11 @@ using namespace std::literals;
 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 @@ MultifileBlobCache::MultifileBlobCache(size_t maxKeySize, size_t maxValueSize, s
         mMaxTotalEntries(maxTotalEntries),
         mTotalCacheSize(0),
         mTotalCacheEntries(0),
+        mTotalCacheSizeDivisor(kCacheLimitDivisor),
         mHotCacheLimit(0),
         mHotCacheSize(0),
         mWorkerThreadIdle(true) {
@@ -247,7 +253,8 @@ MultifileBlobCache::MultifileBlobCache(size_t maxKeySize, size_t maxValueSize, s
                 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 @@ void MultifileBlobCache::set(const void* key, EGLsizeiANDROID keySize, const voi
     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 @@ EGLsizeiANDROID MultifileBlobCache::get(const void* key, EGLsizeiANDROID keySize
     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 @@ EGLsizeiANDROID MultifileBlobCache::get(const void* key, EGLsizeiANDROID keySize
         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 @@ EGLsizeiANDROID MultifileBlobCache::get(const void* key, EGLsizeiANDROID keySize
         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 @@ bool MultifileBlobCache::checkStatus(const std::string& baseDir) {
 }
 
 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 @@ bool MultifileBlobCache::removeEntry(uint32_t entryHash) {
         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 @@ bool MultifileBlobCache::contains(uint32_t hashEntry) const {
 }
 
 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::removeFromHotCache(uint32_t entryHash) {
 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 @@ bool MultifileBlobCache::clearCache() {
     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 @@ void MultifileBlobCache::trimCache() {
     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 @@ void MultifileBlobCache::processTask(DeferredTask& task) {
                 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 fe477bc76a..3bd393f068 100644
--- a/opengl/libs/EGL/MultifileBlobCache.h
+++ b/opengl/libs/EGL/MultifileBlobCache.h
@@ -49,9 +49,9 @@ struct MultifileHeader {
 };
 
 struct MultifileEntryStats {
+    uint32_t entryHash;
     EGLsizeiANDROID valueSize;
     size_t fileSize;
-    time_t accessTime;
 };
 
 struct MultifileStatus {
@@ -104,6 +104,26 @@ private:
     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 @@ public:
 
     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 @@ public:
 
 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 @@ private:
     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 @@ private:
     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 c95bf28650..74352d477d 100644
--- a/opengl/libs/EGL/MultifileBlobCache_test.cpp
+++ b/opengl/libs/EGL/MultifileBlobCache_test.cpp
@@ -318,7 +318,7 @@ std::vector<std::string> MultifileBlobCacheTest::getCacheEntries() {
 
     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 @@ std::vector<std::string> MultifileBlobCacheTest::getCacheEntries() {
                 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 @@ TEST_F(MultifileBlobCacheTest, SameKeyLargeValues) {
     }
 }
 
+// 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