feat: Improve automatic cache cleanup mechanism

The cache cleanup mechanism has worked essentially the same ever since
ccache was initially created in 2002:

- The total number and size of all files in one of the 16 subdirectories
  (AKA level 1) are kept in the stats file in said subdirectory.
- On a cache miss, the new compilation result file is written (based on
  the first digits of the hash) to a subdirectory of one of those 16
  subdirectories, and the stats file is updated accordingly.
- Automatic cleanup is triggered if the size of the level 1 subdirectory
  becomes larger than max_size / 16.
- ccache then lists all files in the subdirectory recursively, stats
  them to check their size and mtime, sorts the file list on mtime and
  deletes the 20% oldest files.

Some problems with the approach described above:

- (A) If several concurrent ccache invocations result in a cache miss
  and write their results to the same subdirectory then all of them will
  start cleaning up the same subdirectory simultaneously, doing
  unnecessary work.
- (B) The ccache invocation that resulted in a cache miss will perform
  cleanup and then exit, which means that an arbitrary ccache process
  that happens to trigger cleanup will take a long time to finish.
- (C) Listing all files in a subdirectory of a large cache can be quite
  slow.
- (D) stat-ing all files in a subdirectory of a large cache can be quite
  slow.
- (E) Deleting many files can be quite slow.
- (F) Since a cleanup by default removes 20% of the files in a
  subdirectory, the actual cache size will (once the cache limit is
  reached) on average hover around 90% of the configured maximum size,
  which can be confusing.

This commit solves or improves on all of the listed problems:

- Before starting automatic cleanup, a global "auto cleanup" lock is
  acquired (non-blocking) so that at most one process is performing
  cleanup at a time. This solves the potential "cache cleanup stampede"
  described in (A).
- Automatic cleanup is now performed in just one of the 256 level 2
  directories. This means that a single cleanup on average will be 16
  times faster than before. This improves on (B), (C), (D) and (E) since
  the cleanup made by a single compilation will not have to access a
  large part of the cache. On the other hand, cleanups will be triggered
  16 times more often, but the cleanup duty will be more evenly spread
  out during a build.
- The total cache size is calculated and compared with the configured
  maximum size before starting automatic cleanup. This, in combination
  with performing cleanup on level 2, means that the actual cache size
  will stay very close to the maximum size instead of about 90%. This
  solves (F).

The limit_multiple configuration option has been removed since it is no
longer used.

Closes #417.

2 files changed, 13 insertions, 3 deletions

diff --git a/src/core/Statistic.hpp b/src/core/Statistic.hpp
index 1f4fb921..ba39cfea 100644
--- a/src/core/Statistic.hpp
+++ b/src/core/Statistic.hpp
@@ -72,7 +72,13 @@ enum class Statistic {
   remote_storage_hit = 47,
   remote_storage_miss = 48,
 
-  END
+  // 49-64: files in level 2 subdirs 0-f
+  subdir_files_base = 49,
+
+  // 65-80: size (KiB) in level 2 subdirs 0-f
+  subdir_size_kibibyte_base = 65,
+
+  END = 81
 };
 
 } // namespace core
diff --git a/src/core/Statistics.cpp b/src/core/Statistics.cpp
index e76ea5e0..459d1f13 100644
--- a/src/core/Statistics.cpp
+++ b/src/core/Statistics.cpp
@@ -127,10 +127,14 @@ const StatisticsField k_statistics_fields[] = {
   FIELD(unsupported_source_language,
         "Unsupported source language",
         FLAG_UNCACHEABLE),
+
+  // subdir_files_base and subdir_size_kibibyte_base are intentionally omitted
+  // since they are not interesting to show.
 };
 
 static_assert(sizeof(k_statistics_fields) / sizeof(k_statistics_fields[0])
-              == static_cast<size_t>(Statistic::END) - 1);
+              == static_cast<size_t>(Statistic::END)
+                   - (/*none*/ 1 + /*subdir files*/ 16 + /*subdir size*/ 16));
 
 static std::string
 format_timestamp(const util::TimePoint& value)
@@ -333,7 +337,7 @@ Statistics::format_human_readable(const Config& config,
     }
     table.add_row(size_cells);
 
-    if (verbosity > 0) {
+    if (verbosity > 0 || config.max_files() > 0) {
       std::vector<C> files_cells{"  Files:", S(files_in_cache)};
       if (config.max_files() > 0) {
         files_cells.emplace_back("/");