[Support][CachePruning] prune least recently accessed files first

Summary:
Before this change, pruning order was based on size. This changes it
to be based on time of last use instead, preferring to keep recently
used files and prune older ones.

Reviewers: pcc, rnk, espindola

Reviewed By: rnk

Subscribers: emaste, arichardson, hiraditya, steven_wu, dexonsmith, llvm-commits

Differential Revision: https://reviews.llvm.org/D51062

llvm-svn: 340374

1 files changed, 35 insertions, 12 deletions

diff --git a/llvm/lib/Support/CachePruning.cpp b/llvm/lib/Support/CachePruning.cpp
index 7326c4fc91f..a0aa6024b3e 100644
--- a/llvm/lib/Support/CachePruning.cpp
+++ b/llvm/lib/Support/CachePruning.cpp
@@ -27,6 +27,28 @@
 
 using namespace llvm;
 
+namespace {
+struct FileInfo {
+  sys::TimePoint<> Time;
+  uint64_t Size;
+  std::string Path;
+
+  /// Used to determine which files to prune first. Also used to determine
+  /// set membership, so must take into account all fields.
+  bool operator<(const FileInfo &Other) const {
+    if (Time < Other.Time)
+      return true;
+    else if (Other.Time < Time)
+      return false;
+    if (Other.Size < Size)
+      return true;
+    else if (Size < Other.Size)
+      return false;
+    return Path < Other.Path;
+  }
+};
+} // anonymous namespace
+
 /// Write a new timestamp file with the given path. This is used for the pruning
 /// interval option.
 static void writeTimestampFile(StringRef TimestampFile) {
@@ -185,8 +207,9 @@ bool llvm::pruneCache(StringRef Path, CachePruningPolicy Policy) {
     writeTimestampFile(TimestampFile);
   }
 
-  // Keep track of space. Needs to be kept ordered by size for determinism.
-  std::set<std::pair<uint64_t, std::string>> FileSizes;
+  // Keep track of files to delete to get below the size limit.
+  // Order by time of last use so that recently used files are preserved.
+  std::set<FileInfo> FileInfos;
   uint64_t TotalSize = 0;
 
   // Walk the entire directory cache, looking for unused files.
@@ -224,22 +247,22 @@ bool llvm::pruneCache(StringRef Path, CachePruningPolicy Policy) {
 
     // Leave it here for now, but add it to the list of size-based pruning.
     TotalSize += StatusOrErr->getSize();
-    FileSizes.insert({StatusOrErr->getSize(), std::string(File->path())});
+    FileInfos.insert({FileAccessTime, StatusOrErr->getSize(), File->path()});
   }
 
-  auto FileAndSize = FileSizes.rbegin();
-  size_t NumFiles = FileSizes.size();
+  auto FileInfo = FileInfos.begin();
+  size_t NumFiles = FileInfos.size();
 
   auto RemoveCacheFile = [&]() {
     // Remove the file.
-    sys::fs::remove(FileAndSize->second);
+    sys::fs::remove(FileInfo->Path);
     // Update size
-    TotalSize -= FileAndSize->first;
+    TotalSize -= FileInfo->Size;
     NumFiles--;
-    LLVM_DEBUG(dbgs() << " - Remove " << FileAndSize->second << " (size "
-                      << FileAndSize->first << "), new occupancy is "
-                      << TotalSize << "%\n");
-    ++FileAndSize;
+    LLVM_DEBUG(dbgs() << " - Remove " << FileInfo->Path << " (size "
+                      << FileInfo->Size << "), new occupancy is " << TotalSize
+                      << "%\n");
+    ++FileInfo;
   };
 
   // Prune for number of files.
@@ -270,7 +293,7 @@ bool llvm::pruneCache(StringRef Path, CachePruningPolicy Policy) {
                       << Policy.MaxSizeBytes << " bytes\n");
 
     // Remove the oldest accessed files first, till we get below the threshold.
-    while (TotalSize > TotalSizeTarget && FileAndSize != FileSizes.rend())
+    while (TotalSize > TotalSizeTarget && FileInfo != FileInfos.end())
       RemoveCacheFile();
   }
   return true;