Add Cache Pruning support

[mehdi_amini]

Summary

Incremental LTO will usea cache to store object files.
This patch handles the pruning part of the cache, exposing
a few knobs:

• Pruning interval: the implementation keeps a "timestamp" file in the directory and will scan it only after a given interval since the last modification of the timestamp file. This is for performance purpose, we don't want to scan continuously the folder.
• Entry expiration: this is the time after which a file that hasn't been used is remove from the cache.
• Maximum size: expressed in percentage of the available disk space, it helps to avoid that we blow up the disk space.

[silvas]

lib/Support/CachePruning.cpp

54

Can you use sys::fs::status? If not, can you add a comment about why not?

[bruno]

It might be worth looking at how clang implements pruning for old modules. The option in question is -fmodules-prune-interval.

[llvm-commits]

This is copy-pasted-adapted from module pruning. I plan to refactor module pruning to use this at some point.

[bruno]

What about:

sys::fs::file_status Status;
if (sys::fs::status(LHS, Status))
  return false;
auto LastModTime = Status.getLastModificationTime();

[mehdi_amini]

This will not help with the access to StatBuf.st_atime.

[bruno]

Not that it should block your progress here, but at some point sys::fs::file_status should be augmented with this info. Can you add a FIXME above the ::stat call and mention that?

include/llvm/Support/CachePruning.h

2

nanage => manage

lib/Support/CachePruning.cpp

2

Director -> Directory

[llvm-commits]

I plan on adding this to sys::fs::file_status indeed, hopefully it is not too hard and this patch can wait for it.

[mehdi_amini]

Use llvm::sys:fs::status() instead of stats.

[mehdi_amini]

Use llvm::sys:fs:disk_space() introduced in D18467

[tejohnson]

lib/Support/CachePruning.cpp

10

Stale description.

102

When would that happen? Not sure what "nothing interesting there" means or if this is an error?

[mehdi_amini]

lib/Support/CachePruning.cpp

102

Just means we can't read this file I guess? (copy pasted from clang module pruning)

[silvas]

lib/Support/CachePruning.cpp

22

Do you still need these includes? I can't find anything using them after staring for a while at the code.

[mehdi_amini]

lib/Support/CachePruning.cpp

22

Oh yeah those aren't needed anymore after the refactoring in sys::filesystem, will cleanup.

[mehdi_amini]

Remove obsolete #include

[mehdi_amini]

Update header description

[mehdi_amini]

Should be ok now

[mehdi_amini]

Anything else to fix or can we move on and fix whatever comes up post-commit?

[mehdi_amini]

r265209
I'll address any comment made post-commit on the list.

[chapuni]

lib/Support/CachePruning.cpp

45

Don't use errno. Fixed in r269565.

[chapuni]

Sure! We should not peek errno unless the context that calls C libraries.

include/llvm/Support/CachePruning.h

+//=- CachePruning.h - Helper to manage the pruning of a cache dir -*- C++ -*-=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements pruning of a directory intended for cache storage, using
+// various policies.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_CACHE_PRUNING_H
+#define LLVM_SUPPORT_CACHE_PRUNING_H
+
+#include "llvm/ADT/StringRef.h"
+
+namespace llvm {
+
+/// Handle pruning a directory provided a path and some options to control what
+/// to prune.
+class CachePruning {
+public:
+  /// Prepare to prune \p Path.
+  CachePruning(StringRef Path) : Path(Path) {}
+
+  /// Define the pruning interval. This is intended to be used to avoid scanning
+  /// the directory too often. It does not impact the decision of which file to
+  /// prune. A value of 0 forces the scan to occurs.
+  CachePruning &setPruningInterval(int PruningInterval) {
+    Interval = PruningInterval;
+    return *this;
+  }
+
+  /// Define the expiration for a file. When a file hasn't been accessed for
+  /// \p ExpireAfter seconds, it is removed from the cache. A value of 0 disable
+  /// the expiration-based pruning.
+  CachePruning &setEntryExpiration(unsigned ExpireAfter) {
+    Expiration = ExpireAfter;
+    return *this;
+  }
+
+  /// Define the maximum size for the cache directory, in terms of percentage of
+  /// the available space on the the disk. Set to 100 to indicate no limit, 50
+  /// to indicate that the cache size will not be left over half the
+  /// available disk space. A value over 100 will be reduced to 100. A value of
+  /// 0 disable the size-based pruning.
+  CachePruning &setMaxSize(unsigned Percentage) {
+    PercentageOfAvailableSpace = std::min(100u, Percentage);
+    return *this;
+  }
+
+  /// Peform pruning using the supplied options, returns true if pruning
+  /// occured, i.e. if PruningInterval was expired.
+  bool prune();
+
+private:
+  // Options that matches the setters above.
+  std::string Path;
+  unsigned Expiration = 0;
+  unsigned Interval = 0;
+  unsigned PercentageOfAvailableSpace = 0;
+};
+
+} // namespace llvm
+
+#endif
 No newline at end of file

lib/Support/CMakeLists.txt

add_llvm_library(LLVMSupport
   APFloat.cpp
   APInt.cpp
   APSInt.cpp
   ARMBuildAttrs.cpp
   ARMWinEH.cpp
   Allocator.cpp
   BlockFrequency.cpp
   BranchProbability.cpp
+  CachePruning.cpp
   circular_raw_ostream.cpp
   COM.cpp
   CommandLine.cpp
   Compression.cpp
   ConvertUTF.c
   ConvertUTFWrapper.cpp
   CrashRecoveryContext.cpp
   DataExtractor.cpp

lib/Support/CachePruning.cpp

+//===-CachePruning.cpp - LLVM Cache Directory Pruning ---------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the Thin Link Time Optimization library. This library is
+// intended to be used by linker to optimize code at link time.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/CachePruning.h"
+
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <set>
+#if defined(__APPLE__)
+#include <sys/mount.h>
+#else
+#include <sys/vfs.h>
+#endif
+
+using namespace llvm;
+
+/// 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);
+}
+
+/// Prune the cache of files that haven't been accessed in a long time.
+bool CachePruning::prune() {
+  SmallString<128> TimestampFile(Path);
+  sys::path::append(TimestampFile, "llvmcache.timestamp");
+
+  if (Expiration == 0 && PercentageOfAvailableSpace == 0)
+    // Nothing will be pruned, early exit
+    return false;
+
+  // Try to stat() the timestamp file.
+  sys::fs::file_status FileStatus;
+  sys::TimeValue CurrentTime = sys::TimeValue::now();
+  if (sys::fs::status(TimestampFile, FileStatus)) {
+    if (errno == ENOENT) {
+      // If the timestamp file wasn't there, create one now.
+      writeTimestampFile(TimestampFile);
+    } else {
+      // Unknown error?
+      return false;
+    }
+  } else {
+    if (Interval) {
+      // Check whether the time stamp is older than our pruning interval.
+      // If not, do nothing.
+      sys::TimeValue TimeStampModTime = FileStatus.getLastModificationTime();
+      auto TimeInterval = sys::TimeValue(sys::TimeValue::SecondsType(Interval));
+      if (CurrentTime - TimeStampModTime <= TimeInterval)
+        return false;
+    }
+    // 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);
+  }
+
+  bool ShouldComputeSize = (PercentageOfAvailableSpace > 0);
+
+  // Keep track of space
+  std::set<std::pair<uint64_t, std::string>> FileSizes;
+  uint64_t TotalSize = 0;
+  // Helper to add a path to the set of files to consider for size-based
+  // pruning, sorted by last accessed time.
+  auto AddToFileListForSizePruning =
+      [&](StringRef Path, sys::TimeValue FileAccessTime) {
+        if (!ShouldComputeSize)
+          return;
+        TotalSize += FileStatus.getSize();
+        FileSizes.insert(
+            std::make_pair(FileAccessTime.seconds(), std::string(Path)));
+      };
+
+  // Walk the entire directory cache, looking for unused files.
+  std::error_code EC;
+  SmallString<128> CachePathNative;
+  sys::path::native(Path, CachePathNative);
+  auto TimeExpiration = sys::TimeValue(sys::TimeValue::SecondsType(Expiration));
+  // Walk all of the files within this directory.
+  for (sys::fs::directory_iterator File(CachePathNative, EC), FileEnd;
+       File != FileEnd && !EC; File.increment(EC)) {
+    // Do not touch the timestamp.
+    if (File->path() == TimestampFile)
+      continue;
+
+    // Look at this file. If we can't stat it, there's nothing interesting
+    // there.
+    if (sys::fs::status(File->path(), FileStatus))
+      continue;
+
+    // If the file hasn't been used recently enough, delete it
+    sys::TimeValue FileAccessTime = FileStatus.getLastAccessedTime();
+    if (CurrentTime - FileAccessTime > TimeExpiration) {
+      sys::fs::remove(File->path());
+      continue;
+    }
+
+    // Leave it here for now, but add it to the list of size-based pruning.
+    AddToFileListForSizePruning(File->path(), FileAccessTime);
+  }
+
+  // Prune for size now if needed
+  if (ShouldComputeSize) {
+    sys::fs::space_info SpaceInfo;
+    if (sys::fs::disk_space(Path, SpaceInfo)) {
+      report_fatal_error("Can't get available size");
+    }
+    auto AvailableSpace = TotalSize + SpaceInfo.free;
+    auto FileAndSize = FileSizes.rbegin();
+    // Remove the oldest accessed files first, till we get below the threshold
+    while (((100 * TotalSize) / AvailableSpace) > PercentageOfAvailableSpace &&
+           FileAndSize != FileSizes.rend()) {
+      // Remove the file.
+      sys::fs::remove(FileAndSize->second);
+      // Update size
+      TotalSize -= FileAndSize->first;
+      ++FileAndSize;
+    }
+  }
+  return true;
+}