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

[inglorion]

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.

[rnk]

lgtm

[inglorion]

update llvm/test/ThinLTO/X86/cache.ll to match the new expectations

[rnk]

lgtm

llvm/test/ThinLTO/X86/cache.ll

109 ↗

(On Diff #161855)

Woah.

lld/trunk/test/ELF/lto/cache.ll

 ; Setting max number of files to 0 should disable the limit, not delete everything.
 ; RUN: ld.lld --thinlto-cache-dir=%t.cache --thinlto-cache-policy prune_after=0s:cache_size=0%:cache_size_files=0:prune_interval=0s -o %t3 %t2.o %t.o
 ; RUN: ls %t.cache | count 4
 
 ; Delete everything except for the timestamp, "foo" and one cache file.
 ; RUN: ld.lld --thinlto-cache-dir=%t.cache --thinlto-cache-policy prune_after=0s:cache_size=0%:cache_size_files=1:prune_interval=0s -o %t3 %t2.o %t.o
 ; RUN: ls %t.cache | count 3
 
+; Check that we remove the least recently used file first.
+; RUN: rm -fr %t.cache
+; RUN: mkdir %t.cache
+; RUN: echo xyz > %t.cache/llvmcache-old
+; RUN: touch -t 198002011200 %t.cache/llvmcache-old
+; RUN: echo xyz > %t.cache/llvmcache-newer
+; RUN: touch -t 198002021200 %t.cache/llvmcache-newer
+; RUN: ld.lld --thinlto-cache-dir=%t.cache --thinlto-cache-policy prune_after=0s:cache_size=0%:cache_size_files=3:prune_interval=0s -o %t3 %t2.o %t.o
+; RUN: ls %t.cache | FileCheck %s
+
+; CHECK-NOT: llvmcache-old
+; CHECK: llvmcache-newer
+; CHECK-NOT: llvmcache-old
+
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @globalfunc() #0 {
 entry:
   ret void
 }

llvm/trunk/lib/Support/CachePruning.cpp

 
 #define DEBUG_TYPE "cache-pruning"
 
 #include <set>
 #include <system_error>
 
 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) {
   std::error_code EC;
   raw_fd_ostream Out(TimestampFile.str(), EC, sys::fs::F_None);
 }
 
 static Expected<std::chrono::seconds> parseDuration(StringRef Duration) {
if (Policy.Interval != seconds(0)) {
       }
     }
     // Write a new timestamp file so that nobody else attempts to prune.
     // There is a benign race condition here, if two processes happen to
     // notice at the same time that the timestamp is out-of-date.
     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.
   std::error_code EC;
   SmallString<128> CachePathNative;
   sys::path::native(Path, CachePathNative);
   // Walk all of the files within this directory.
   for (sys::fs::directory_iterator File(CachePathNative, EC), FileEnd;
if (Policy.Expiration != seconds(0) && FileAge > Policy.Expiration) {
                         << duration_cast<seconds>(FileAge).count()
                         << "s old)\n");
       sys::fs::remove(File->path());
       continue;
     }
 
     // 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.
   if (Policy.MaxSizeFiles)
     while (NumFiles > Policy.MaxSizeFiles)
       RemoveCacheFile();
 
   // Prune for size now if needed
auto TotalSizeTarget = std::min<uint64_t>(
         Policy.MaxSizeBytes);
 
     LLVM_DEBUG(dbgs() << "Occupancy: " << ((100 * TotalSize) / AvailableSpace)
                       << "% target is: "
                       << Policy.MaxSizePercentageOfAvailableSpace << "%, "
                       << 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;
 }

llvm/trunk/test/ThinLTO/X86/cache.ll

 ; RUN: touch -a -t 197001011200 %t.cache/llvmcache-*
 ; RUN: llvm-lto2 run -o %t.o %t2.bc %t.bc -cache-dir %t.cache \
 ; RUN:  -r=%t2.bc,_main,plx \
 ; RUN:  -r=%t2.bc,_globalfunc,lx \
 ; RUN:  -r=%t.bc,_globalfunc,plx
 ; RUN: ls -ltu %t.cache/* | not grep 1970-01-01
 
 ; Verify that specifying max size for the cache directory prunes it to this
-; size, removing the largest files first.
+; size, removing the oldest files first.
 ; RUN: rm -Rf %t.cache && mkdir %t.cache
 ; Create cache files with different sizes.
-; Only 8B, 16B and 76B files should stay after pruning.
-; RUN: %python -c "with open(r'%t.cache/llvmcache-foo-1024', 'w') as file: file.truncate(1024)"
-; RUN: %python -c "with open(r'%t.cache/llvmcache-foo-16', 'w') as file: file.truncate(16)"
-; RUN: %python -c "with open(r'%t.cache/llvmcache-foo-8', 'w') as file: file.truncate(8)"
-; RUN: %python -c "with open(r'%t.cache/llvmcache-foo-76', 'w') as file: file.truncate(76)"
-; RUN: %python -c "with open(r'%t.cache/llvmcache-foo-77', 'w') as file: file.truncate(77)"
-; RUN: llvm-lto -thinlto-action=run -exported-symbol=globalfunc %t2.bc %t.bc -thinlto-cache-dir %t.cache --thinlto-cache-max-size-bytes 100
-; RUN: ls %t.cache/llvmcache-foo-16
+; Only 8B and 76B files should stay after pruning.
+; RUN: "%python" -c "with open(r'%t.cache/llvmcache-foo-100k', 'w') as file: file.truncate(102400)"
+; RUN: touch -t 198002011200 %t.cache/llvmcache-foo-100k
+; RUN: "%python" -c "with open(r'%t.cache/llvmcache-foo-16', 'w') as file: file.truncate(16)"
+; RUN: touch -t 198002021200 %t.cache/llvmcache-foo-16
+; RUN: "%python" -c "with open(r'%t.cache/llvmcache-foo-77k', 'w') as file: file.truncate(78848)"
+; RUN: touch -t 198002031200 %t.cache/llvmcache-foo-77k
+; RUN: "%python" -c "with open(r'%t.cache/llvmcache-foo-8', 'w') as file: file.truncate(8)"
+; RUN: "%python" -c "with open(r'%t.cache/llvmcache-foo-76', 'w') as file: file.truncate(76)"
+; RUN: llvm-lto -thinlto-action=run -exported-symbol=globalfunc %t2.bc %t.bc -thinlto-cache-dir %t.cache --thinlto-cache-max-size-bytes 78847
 ; RUN: ls %t.cache/llvmcache-foo-8
 ; RUN: ls %t.cache/llvmcache-foo-76
-; RUN: not ls %t.cache/llvmcache-foo-1024
-; RUN: not ls %t.cache/llvmcache-foo-77
+; RUN: not ls %t.cache/llvmcache-foo-16
+; RUN: not ls %t.cache/llvmcache-foo-100k
+; RUN: not ls %t.cache/llvmcache-foo-77k
 
 ; Verify that specifying max number of files in the cache directory prunes
-; it to this amount, removing the largest files first.
+; it to this amount, removing the oldest files first.
 ; RUN: rm -Rf %t.cache && mkdir %t.cache
 ; Create cache files with different sizes.
-; Only 8B and 16B files should stay after pruning.
-; RUN: %python -c "print(' ' * 1023)" > %t.cache/llvmcache-foo-1024
-; RUN: %python -c "print(' ' * 15)" > %t.cache/llvmcache-foo-16
-; RUN: %python -c "print(' ' * 7)" > %t.cache/llvmcache-foo-8
-; RUN: %python -c "print(' ' * 75)" > %t.cache/llvmcache-foo-76
-; RUN: %python -c "print(' ' * 76)" > %t.cache/llvmcache-foo-77
-; RUN: llvm-lto -thinlto-action=run -exported-symbol=globalfunc %t2.bc %t.bc -thinlto-cache-dir %t.cache --thinlto-cache-max-size-files 2
-; RUN: ls %t.cache/llvmcache-foo-16
-; RUN: ls %t.cache/llvmcache-foo-8
-; RUN: not ls %t.cache/llvmcache-foo-76
+; Only 75B and 76B files should stay after pruning.
+; RUN: "%python" -c "print(' ' * 1023)" > %t.cache/llvmcache-foo-1023
+; RUN: touch -t 198002011200 %t.cache/llvmcache-foo-1023
+; RUN: "%python" -c "print(' ' * 15)" > %t.cache/llvmcache-foo-15
+; RUN: touch -t 198002021200 %t.cache/llvmcache-foo-15
+; RUN: "%python" -c "print(' ' * 7)" > %t.cache/llvmcache-foo-7
+; RUN: touch -t 198002031200 %t.cache/llvmcache-foo-7
+; RUN: "%python" -c "print(' ' * 75)" > %t.cache/llvmcache-foo-75
+; RUN: "%python" -c "print(' ' * 76)" > %t.cache/llvmcache-foo-76
+; RUN: llvm-lto -thinlto-action=run -exported-symbol=globalfunc %t2.bc %t.bc -thinlto-cache-dir %t.cache --thinlto-cache-max-size-files 4
+; RUN: ls %t.cache/llvmcache-foo-75
+; RUN: ls %t.cache/llvmcache-foo-76
+; RUN: not ls %t.cache/llvmcache-foo-15
 ; RUN: not ls %t.cache/llvmcache-foo-1024
-; RUN: not ls %t.cache/llvmcache-foo-77
+; RUN: not ls %t.cache/llvmcache-foo-7
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.11.0"
 
 define void @globalfunc() #0 {
 entry:
   ret void
 }