path: root/src/storage/local/LocalStorage.cpp

// Copyright (C) 2021-2023 Joel Rosdahl and other contributors
//
// See doc/AUTHORS.adoc for a complete list of contributors.
//
// This program is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 3 of the License, or (at your option)
// any later version.
//
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
// more details.
//
// You should have received a copy of the GNU General Public License along with
// this program; if not, write to the Free Software Foundation, Inc., 51
// Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

#include "LocalStorage.hpp"

#include <AtomicFile.hpp>
#include <Config.hpp>
#include <Context.hpp>
#include <File.hpp>
#include <Logging.hpp>
#include <MiniTrace.hpp>
#include <TemporaryFile.hpp>
#include <ThreadPool.hpp>
#include <Util.hpp>
#include <assertions.hpp>
#include <core/CacheEntry.hpp>
#include <core/FileRecompressor.hpp>
#include <core/Manifest.hpp>
#include <core/Result.hpp>
#include <core/Statistics.hpp>
#include <core/exceptions.hpp>
#include <core/wincompat.hpp>
#include <fmtmacros.hpp>
#include <storage/local/StatsFile.hpp>
#include <storage/local/util.hpp>
#include <util/Duration.hpp>
#include <util/expected.hpp>
#include <util/file.hpp>
#include <util/string.hpp>

#include <third_party/fmt/core.h>

#ifdef INODE_CACHE_SUPPORTED
#  include <InodeCache.hpp>
#endif

#include <algorithm>
#include <atomic>
#include <memory>
#include <string>

#ifdef HAVE_UNISTD_H
#  include <unistd.h>
#endif

using core::Statistic;

namespace storage::local {

// How often (in seconds) to scan $CCACHE_DIR/tmp for left-over temporary
// files.
const util::Duration k_tempdir_cleanup_interval(2 * 24 * 60 * 60); // 2 days

// Maximum files per cache directory. This constant is somewhat arbitrarily
// chosen to be large enough to avoid unnecessary cache levels but small enough
// not to make it too slow for legacy file systems with bad performance for
// large directories. It could be made configurable, but hopefully there will be
// no need to do that.
const uint64_t k_max_cache_files_per_directory = 2000;

// Minimum number of cache levels ($CCACHE_DIR/1/2/stored_file).
const uint8_t k_min_cache_levels = 2;

// Maximum number of cache levels ($CCACHE_DIR/1/2/3/stored_file).
//
// On a cache miss, (k_max_cache_levels - k_min_cache_levels + 1) cache lookups
// (i.e. stat system calls) will be performed for a cache entry.
//
// An assumption made here is that if a cache is so large that it holds more
// than 16^4 * k_max_cache_files_per_directory files then we can assume that the
// file system is sane enough to handle more than
// k_max_cache_files_per_directory.
const uint8_t k_max_cache_levels = 4;

namespace {

struct SubdirCounters
{
  uint64_t files = 0;
  uint64_t size = 0;
  uint64_t cleanups_performed = 0;

  SubdirCounters&
  operator+=(const SubdirCounters& other)
  {
    files += other.files;
    size += other.size;
    cleanups_performed += other.cleanups_performed;
    return *this;
  }
};

} // namespace

static void
set_counters(const std::string& level_1_dir, const SubdirCounters& level_1_cs)
{
  const std::string stats_file = level_1_dir + "/stats";
  StatsFile(stats_file).update([&](auto& cs) {
    cs.increment(Statistic::cleanups_performed, level_1_cs.cleanups_performed);
    cs.set(Statistic::files_in_cache, level_1_cs.files);
    cs.set(Statistic::cache_size_kibibyte, level_1_cs.size / 1024);
  });
}

static std::string
suffix_from_type(const core::CacheEntryType type)
{
  switch (type) {
  case core::CacheEntryType::manifest:
    return "M";

  case core::CacheEntryType::result:
    return "R";
  }

  ASSERT(false);
}

static uint8_t
calculate_wanted_cache_level(const uint64_t files_in_level_1)
{
  uint64_t files_per_directory = files_in_level_1 / 16;
  for (uint8_t i = k_min_cache_levels; i <= k_max_cache_levels; ++i) {
    if (files_per_directory < k_max_cache_files_per_directory) {
      return i;
    }
    files_per_directory /= 16;
  }
  return k_max_cache_levels;
}

static void
delete_file(const std::string& path,
            const uint64_t size,
            uint64_t* cache_size,
            uint64_t* files_in_cache)
{
  const bool deleted = Util::unlink_safe(path, Util::UnlinkLog::ignore_failure);
  if (!deleted && errno != ENOENT && errno != ESTALE) {
    LOG("Failed to unlink {} ({})", path, strerror(errno));
  } else if (cache_size && files_in_cache) {
    // The counters are intentionally subtracted even if there was no file to
    // delete since the final cache size calculation will be incorrect if they
    // aren't. (This can happen when there are several parallel ongoing
    // cleanups of the same directory.)
    *cache_size -= size;
    --*files_in_cache;
  }
}

static SubdirCounters
clean_dir(const std::string& subdir,
          const uint64_t max_size,
          const uint64_t max_files,
          const std::optional<uint64_t> max_age,
          const std::optional<std::string> namespace_,
          const ProgressReceiver& progress_receiver)
{
  LOG("Cleaning up cache directory {}", subdir);

  auto files = get_cache_dir_files(subdir);
  progress_receiver(1.0 / 3);

  uint64_t cache_size = 0;
  uint64_t files_in_cache = 0;
  auto current_time = util::TimePoint::now();
  std::unordered_map<std::string /*result_file*/,
                     std::vector<std::string> /*associated_raw_files*/>
    raw_files_map;

  for (size_t i = 0; i < files.size();
       ++i, progress_receiver(1.0 / 3 + 1.0 * i / files.size() / 3)) {
    const auto& file = files[i];

    if (!file.is_regular()) {
      // Not a file or missing file.
      continue;
    }

    // Delete any tmp files older than 1 hour right away.
    if (file.mtime() + util::Duration(3600) < current_time
        && TemporaryFile::is_tmp_file(file.path())) {
      Util::unlink_tmp(file.path());
      continue;
    }

    if (namespace_ && file_type_from_path(file.path()) == FileType::raw) {
      const auto result_filename =
        FMT("{}R", file.path().substr(0, file.path().length() - 2));
      raw_files_map[result_filename].push_back(file.path());
    }

    cache_size += file.size_on_disk();
    files_in_cache += 1;
  }

  // Sort according to modification time, oldest first.
  std::sort(files.begin(), files.end(), [](const auto& f1, const auto& f2) {
    return f1.mtime() < f2.mtime();
  });

  LOG("Before cleanup: {:.0f} KiB, {:.0f} files",
      static_cast<double>(cache_size) / 1024,
      static_cast<double>(files_in_cache));

  bool cleaned = false;
  for (size_t i = 0; i < files.size();
       ++i, progress_receiver(2.0 / 3 + 1.0 * i / files.size() / 3)) {
    const auto& file = files[i];

    if (!file || file.is_directory()) {
      continue;
    }

    if ((max_size == 0 || cache_size <= max_size)
        && (max_files == 0 || files_in_cache <= max_files)
        && (!max_age
            || file.mtime() > (current_time - util::Duration(*max_age)))
        && (!namespace_ || max_age)) {
      break;
    }

    if (namespace_) {
      try {
        core::CacheEntry::Header header(file.path());
        if (header.namespace_ != *namespace_) {
          continue;
        }
      } catch (core::Error&) {
        // Failed to read header: ignore.
        continue;
      }

      // For namespace eviction we need to remove raw files based on result
      // filename since they don't have a header.
      if (file_type_from_path(file.path()) == FileType::result) {
        const auto entry = raw_files_map.find(file.path());
        if (entry != raw_files_map.end()) {
          for (const auto& raw_file : entry->second) {
            delete_file(raw_file,
                        Stat::lstat(raw_file).size_on_disk(),
                        &cache_size,
                        &files_in_cache);
          }
        }
      }
    }

    delete_file(file.path(), file.size_on_disk(), &cache_size, &files_in_cache);
    cleaned = true;
  }

  LOG("After cleanup: {:.0f} KiB, {:.0f} files",
      static_cast<double>(cache_size) / 1024,
      static_cast<double>(files_in_cache));

  if (cleaned) {
    LOG("Cleaned up cache directory {}", subdir);
  }

  return SubdirCounters{files_in_cache, cache_size, cleaned ? 1U : 0U};
}

FileType
file_type_from_path(std::string_view path)
{
  if (util::ends_with(path, "M")) {
    return FileType::manifest;
  } else if (util::ends_with(path, "R")) {
    return FileType::result;
  } else if (util::ends_with(path, "W")) {
    return FileType::raw;
  } else {
    return FileType::unknown;
  }
}

LocalStorage::LocalStorage(const Config& config) : m_config(config)
{
}

void
LocalStorage::finalize()
{
  if (m_config.temporary_dir() == m_config.default_temporary_dir()) {
    clean_internal_tempdir();
  }

  if (!m_config.stats()) {
    return;
  }

  if (m_manifest_key) {
    // A manifest entry was written.
    ASSERT(!m_manifest_path.empty());
    update_stats_and_maybe_move_cache_file(*m_manifest_key,
                                           m_manifest_path,
                                           m_manifest_counter_updates,
                                           core::CacheEntryType::manifest);
  }

  if (!m_result_key) {
    // No result entry was written, so we just choose one of the stats files in
    // the 256 level 2 directories.

    ASSERT(m_result_counter_updates.get(Statistic::cache_size_kibibyte) == 0);
    ASSERT(m_result_counter_updates.get(Statistic::files_in_cache) == 0);

    const auto bucket = getpid() % 256;
    const auto stats_file =
      FMT("{}/{:x}/{:x}/stats", m_config.cache_dir(), bucket / 16, bucket % 16);
    StatsFile(stats_file).update([&](auto& cs) {
      cs.increment(m_result_counter_updates);
    });
    return;
  }

  ASSERT(!m_result_path.empty());

  const auto counters =
    update_stats_and_maybe_move_cache_file(*m_result_key,
                                           m_result_path,
                                           m_result_counter_updates,
                                           core::CacheEntryType::result);
  if (!counters) {
    return;
  }

  const auto subdir =
    FMT("{}/{:x}", m_config.cache_dir(), m_result_key->bytes()[0] >> 4);
  bool need_cleanup = false;

  if (m_config.max_files() != 0
      && counters->get(Statistic::files_in_cache) > m_config.max_files() / 16) {
    LOG("Need to clean up {} since it holds {} files (limit: {} files)",
        subdir,
        counters->get(Statistic::files_in_cache),
        m_config.max_files() / 16);
    need_cleanup = true;
  }
  if (m_config.max_size() != 0
      && counters->get(Statistic::cache_size_kibibyte)
           > m_config.max_size() / 1024 / 16) {
    LOG("Need to clean up {} since it holds {} KiB (limit: {} KiB)",
        subdir,
        counters->get(Statistic::cache_size_kibibyte),
        m_config.max_size() / 1024 / 16);
    need_cleanup = true;
  }

  if (need_cleanup) {
    const double factor = m_config.limit_multiple() / 16;
    const uint64_t max_size = round(m_config.max_size() * factor);
    const uint64_t max_files = round(m_config.max_files() * factor);
    auto level_1_cs = clean_dir(subdir,
                                max_size,
                                max_files,
                                std::nullopt,
                                std::nullopt,
                                [](double /*progress*/) {});
    set_counters(subdir, level_1_cs);
  }
}

std::optional<util::Bytes>
LocalStorage::get(const Digest& key, const core::CacheEntryType type)
{
  MTR_SCOPE("local_storage", "get");

  std::optional<util::Bytes> return_value;

  const auto cache_file = look_up_cache_file(key, type);
  if (cache_file.stat) {
    const auto value = util::read_file<util::Bytes>(cache_file.path);
    if (value) {
      LOG("Retrieved {} from local storage ({})",
          key.to_string(),
          cache_file.path);

      // Update modification timestamp to save file from LRU cleanup.
      util::set_timestamps(cache_file.path);

      return_value = *value;
    } else {
      LOG("Failed to read {}: {}", cache_file.path, value.error());
    }
  } else {
    LOG("No {} in local storage", key.to_string());
  }

  increment_statistic(return_value ? core::Statistic::local_storage_read_hit
                                   : core::Statistic::local_storage_read_miss);
  if (return_value && type == core::CacheEntryType::result) {
    increment_statistic(core::Statistic::local_storage_hit);
  }

  return return_value;
}

void
LocalStorage::put(const Digest& key,
                  const core::CacheEntryType type,
                  nonstd::span<const uint8_t> value,
                  bool only_if_missing)
{
  MTR_SCOPE("local_storage", "put");

  const auto cache_file = look_up_cache_file(key, type);
  if (only_if_missing && cache_file.stat) {
    LOG("Not storing {} in local storage since it already exists",
        cache_file.path);
    return;
  }

  switch (type) {
  case core::CacheEntryType::manifest:
    m_manifest_key = key;
    m_manifest_path = cache_file.path;
    break;

  case core::CacheEntryType::result:
    m_result_key = key;
    m_result_path = cache_file.path;
    break;
  }

  try {
    increment_statistic(core::Statistic::local_storage_write);
    AtomicFile result_file(cache_file.path, AtomicFile::Mode::binary);
    result_file.write(value);
    result_file.commit();
  } catch (core::Error& e) {
    LOG("Failed to write to {}: {}", cache_file.path, e.what());
    return;
  }

  const auto new_stat = Stat::stat(cache_file.path, Stat::OnError::log);
  if (!new_stat) {
    LOG("Failed to stat {}: {}", cache_file.path, strerror(errno));
    return;
  }

  LOG("Stored {} in local storage ({})", key.to_string(), cache_file.path);

  auto& counter_updates = (type == core::CacheEntryType::manifest)
                            ? m_manifest_counter_updates
                            : m_result_counter_updates;
  counter_updates.increment(
    Statistic::cache_size_kibibyte,
    Util::size_change_kibibyte(cache_file.stat, new_stat));
  counter_updates.increment(Statistic::files_in_cache, cache_file.stat ? 0 : 1);

  // Make sure we have a CACHEDIR.TAG in the cache part of cache_dir. This can
  // be done almost anywhere, but we might as well do it near the end as we save
  // the stat call if we exit early.
  util::create_cachedir_tag(
    FMT("{}/{}", m_config.cache_dir(), key.to_string()[0]));
}

void
LocalStorage::remove(const Digest& key, const core::CacheEntryType type)
{
  MTR_SCOPE("local_storage", "remove");

  const auto cache_file = look_up_cache_file(key, type);
  if (cache_file.stat) {
    increment_statistic(core::Statistic::local_storage_write);
    Util::unlink_safe(cache_file.path);
    LOG("Removed {} from local storage ({})", key.to_string(), cache_file.path);
  } else {
    LOG("No {} to remove from local storage", key.to_string());
  }
}

std::string
LocalStorage::get_raw_file_path(std::string_view result_path,
                                uint8_t file_number)
{
  if (file_number >= 10) {
    // To support more entries in the future, encode to [0-9a-z]. Note that
    // LocalStorage::evict currently assumes that the entry number is
    // represented as one character.
    throw core::Error(FMT("Too high raw file entry number: {}", file_number));
  }

  const auto prefix = result_path.substr(0, result_path.length() - 1);
  return FMT("{}{}W", prefix, file_number);
}

std::string
LocalStorage::get_raw_file_path(const Digest& result_key,
                                uint8_t file_number) const
{
  const auto cache_file =
    look_up_cache_file(result_key, core::CacheEntryType::result);
  return get_raw_file_path(cache_file.path, file_number);
}

void
LocalStorage::put_raw_files(
  const Digest& key,
  const std::vector<core::Result::Serializer::RawFile> raw_files)
{
  const auto cache_file = look_up_cache_file(key, core::CacheEntryType::result);
  Util::ensure_dir_exists(Util::dir_name(cache_file.path));

  for (auto [file_number, source_path] : raw_files) {
    const auto dest_path = get_raw_file_path(cache_file.path, file_number);
    const auto old_stat = Stat::stat(dest_path);
    try {
      Util::clone_hard_link_or_copy_file(
        m_config, source_path, dest_path, true);
      m_added_raw_files.push_back(dest_path);
    } catch (core::Error& e) {
      LOG("Failed to store {} as raw file {}: {}",
          source_path,
          dest_path,
          e.what());
      throw;
    }
    const auto new_stat = Stat::stat(dest_path);
    increment_statistic(Statistic::cache_size_kibibyte,
                        Util::size_change_kibibyte(old_stat, new_stat));
    increment_statistic(Statistic::files_in_cache,
                        (new_stat ? 1 : 0) - (old_stat ? 1 : 0));
  }
}

void
LocalStorage::increment_statistic(const Statistic statistic,
                                  const int64_t value)
{
  m_result_counter_updates.increment(statistic, value);
}

void
LocalStorage::increment_statistics(const core::StatisticsCounters& statistics)
{
  m_result_counter_updates.increment(statistics);
}

// Zero all statistics counters except those tracking cache size and number of
// files in the cache.
void
LocalStorage::zero_all_statistics()
{
  const auto now = util::TimePoint::now();
  const auto zeroable_fields = core::Statistics::get_zeroable_fields();

  for_each_level_1_and_2_stats_file(
    m_config.cache_dir(), [=](const std::string& path) {
      StatsFile(path).update([=](auto& cs) {
        for (const auto statistic : zeroable_fields) {
          cs.set(statistic, 0);
        }
        cs.set(core::Statistic::stats_zeroed_timestamp, now.sec());
      });
    });
}

// Get statistics and last time of update for the whole local storage cache.
std::pair<core::StatisticsCounters, util::TimePoint>
LocalStorage::get_all_statistics() const
{
  core::StatisticsCounters counters;
  uint64_t zero_timestamp = 0;
  util::TimePoint last_updated;

  // Add up the stats in each directory.
  for_each_level_1_and_2_stats_file(
    m_config.cache_dir(), [&](const auto& path) {
      counters.set(core::Statistic::stats_zeroed_timestamp, 0); // Don't add
      counters.increment(StatsFile(path).read());
      zero_timestamp = std::max(
        counters.get(core::Statistic::stats_zeroed_timestamp), zero_timestamp);
      last_updated = std::max(last_updated, Stat::stat(path).mtime());
    });

  counters.set(core::Statistic::stats_zeroed_timestamp, zero_timestamp);
  return std::make_pair(counters, last_updated);
}

void
LocalStorage::evict(const ProgressReceiver& progress_receiver,
                    std::optional<uint64_t> max_age,
                    std::optional<std::string> namespace_)
{
  for_each_cache_subdir(
    m_config.cache_dir(),
    progress_receiver,
    [&](const auto& level_1_dir, const auto& level_1_progress_receiver) {
      SubdirCounters counters;
      for_each_cache_subdir(
        level_1_dir,
        level_1_progress_receiver,
        [&](const std::string& level_2_dir,
            const ProgressReceiver& level_2_progress_receiver) {
          counters += clean_dir(
            level_2_dir, 0, 0, max_age, namespace_, level_2_progress_receiver);
        });

      set_counters(level_1_dir, counters);
    });
}

// Clean up all cache subdirectories.
void
LocalStorage::clean_all(const ProgressReceiver& progress_receiver)
{
  for_each_cache_subdir(
    m_config.cache_dir(),
    progress_receiver,
    [&](const auto& level_1_dir, const auto& level_1_progress_receiver) {
      SubdirCounters counters;
      for_each_cache_subdir(
        level_1_dir,
        level_1_progress_receiver,
        [&](const std::string& level_2_dir,
            const ProgressReceiver& level_2_progress_receiver) {
          counters += clean_dir(level_2_dir,
                                m_config.max_size() / 256,
                                m_config.max_files() / 16,
                                std::nullopt,
                                std::nullopt,
                                level_2_progress_receiver);
        });
      set_counters(level_1_dir, counters);
    });
}

// Wipe all cached files in all subdirectories.
void
LocalStorage::wipe_all(const ProgressReceiver& progress_receiver)
{
  for_each_cache_subdir(
    m_config.cache_dir(),
    progress_receiver,
    [&](const auto& level_1_dir, const auto& level_1_progress_receiver) {
      uint64_t cleanups = 0;
      for_each_cache_subdir(
        level_1_dir,
        level_1_progress_receiver,
        [&](const std::string& level_2_dir,
            const ProgressReceiver& level_2_progress_receiver) {
          LOG("Clearing out cache directory {}", level_2_dir);

          const auto files = get_cache_dir_files(level_2_dir);
          level_2_progress_receiver(0.5);

          for (size_t i = 0; i < files.size(); ++i) {
            Util::unlink_safe(files[i].path());
            level_2_progress_receiver(0.5 + 0.5 * i / files.size());
          }

          if (!files.empty()) {
            ++cleanups;
            LOG("Cleared out cache directory {}", level_2_dir);
          }
        });

      set_counters(level_1_dir, SubdirCounters{0, 0, cleanups});
    });
}

CompressionStatistics
LocalStorage::get_compression_statistics(
  const ProgressReceiver& progress_receiver) const
{
  CompressionStatistics cs{};

  for_each_cache_subdir(
    m_config.cache_dir(),
    progress_receiver,
    [&](const auto& level_1_dir, const auto& level_1_progress_receiver) {
      for_each_cache_subdir(
        level_1_dir,
        level_1_progress_receiver,
        [&](const auto& level_2_dir, const auto& level_2_progress_receiver) {
          const auto files = get_cache_dir_files(level_2_dir);
          level_2_progress_receiver(0.2);

          for (size_t i = 0; i < files.size(); ++i) {
            const auto& cache_file = files[i];
            cs.on_disk_size += cache_file.size_on_disk();
            try {
              core::CacheEntry::Header header(cache_file.path());
              cs.compr_size += cache_file.size();
              cs.content_size += header.entry_size;
            } catch (core::Error&) {
              cs.incompr_size += cache_file.size();
            }
            level_2_progress_receiver(0.2 + 0.8 * i / files.size());
          }
        });
    });

  return cs;
}

void
LocalStorage::recompress(const std::optional<int8_t> level,
                         const uint32_t threads,
                         const ProgressReceiver& progress_receiver)
{
  const size_t read_ahead =
    std::max(static_cast<size_t>(10), 2 * static_cast<size_t>(threads));
  ThreadPool thread_pool(threads, read_ahead);
  core::FileRecompressor recompressor;

  std::atomic<uint64_t> incompressible_size = 0;

  for_each_cache_subdir(
    m_config.cache_dir(),
    progress_receiver,
    [&](const auto& level_1_dir, const auto& level_1_progress_receiver) {
      for_each_cache_subdir(
        level_1_dir,
        level_1_progress_receiver,
        [&](const auto& level_2_dir, const auto& level_2_progress_receiver) {
          (void)level_2_progress_receiver;
          (void)level_2_dir;
          auto files = get_cache_dir_files(level_2_dir);
          level_2_progress_receiver(0.1);

          auto stats_file = FMT("{}/stats", Util::dir_name(level_1_dir));

          for (size_t i = 0; i < files.size(); ++i) {
            const auto& file = files[i];

            if (file_type_from_path(file.path()) != FileType::unknown) {
              thread_pool.enqueue(
                [&recompressor, &incompressible_size, level, stats_file, file] {
                  try {
                    Stat new_stat = recompressor.recompress(
                      file, level, core::FileRecompressor::KeepAtime::no);
                    auto size_change_kibibyte =
                      Util::size_change_kibibyte(file, new_stat);
                    if (size_change_kibibyte != 0) {
                      StatsFile(stats_file).update([=](auto& cs) {
                        cs.increment(core::Statistic::cache_size_kibibyte,
                                     size_change_kibibyte);
                      });
                    }
                  } catch (core::Error&) {
                    // Ignore for now.
                    incompressible_size += file.size_on_disk();
                  }
                });
            } else if (!TemporaryFile::is_tmp_file(file.path())) {
              incompressible_size += file.size_on_disk();
            }

            level_2_progress_receiver(0.1 + 0.9 * i / files.size());
          }

          if (util::ends_with(level_2_dir, "f/f")) {
            // Wait here instead of after for_each_cache_subdir to avoid
            // updating the progress bar to 100% before all work is done.
            thread_pool.shut_down();
          }
        });
    });

  // In case there was no f/f subdir, shut down the thread pool now.
  thread_pool.shut_down();

  if (isatty(STDOUT_FILENO)) {
    PRINT_RAW(stdout, "\n\n");
  }

  const double old_ratio = recompressor.old_size() > 0
                             ? static_cast<double>(recompressor.content_size())
                                 / recompressor.old_size()
                             : 0.0;
  const double old_savings =
    old_ratio > 0.0 ? 100.0 - (100.0 / old_ratio) : 0.0;
  const double new_ratio = recompressor.new_size() > 0
                             ? static_cast<double>(recompressor.content_size())
                                 / recompressor.new_size()
                             : 0.0;
  const double new_savings =
    new_ratio > 0.0 ? 100.0 - (100.0 / new_ratio) : 0.0;
  const int64_t size_difference =
    static_cast<int64_t>(recompressor.new_size())
    - static_cast<int64_t>(recompressor.old_size());

  const std::string old_compr_size_str =
    Util::format_human_readable_size(recompressor.old_size());
  const std::string new_compr_size_str =
    Util::format_human_readable_size(recompressor.new_size());
  const std::string content_size_str =
    Util::format_human_readable_size(recompressor.content_size());
  const std::string incompr_size_str =
    Util::format_human_readable_size(incompressible_size);
  const std::string size_difference_str =
    FMT("{}{}",
        size_difference < 0 ? "-" : (size_difference > 0 ? "+" : " "),
        Util::format_human_readable_size(
          size_difference < 0 ? -size_difference : size_difference));

  PRINT(stdout, "Original data:         {:>8s}\n", content_size_str);
  PRINT(stdout,
        "Old compressed data:   {:>8s} ({:.1f}% of original size)\n",
        old_compr_size_str,
        100.0 - old_savings);
  PRINT(stdout,
        "  - Compression ratio: {:>5.3f} x  ({:.1f}% space savings)\n",
        old_ratio,
        old_savings);
  PRINT(stdout,
        "New compressed data:   {:>8s} ({:.1f}% of original size)\n",
        new_compr_size_str,
        100.0 - new_savings);
  PRINT(stdout,
        "  - Compression ratio: {:>5.3f} x  ({:.1f}% space savings)\n",
        new_ratio,
        new_savings);
  PRINT(stdout, "Size change:          {:>9s}\n", size_difference_str);
}

// Private methods

LocalStorage::LookUpCacheFileResult
LocalStorage::look_up_cache_file(const Digest& key,
                                 const core::CacheEntryType type) const
{
  const auto key_string = FMT("{}{}", key.to_string(), suffix_from_type(type));

  for (uint8_t level = k_min_cache_levels; level <= k_max_cache_levels;
       ++level) {
    const auto path = get_path_in_cache(level, key_string);
    const auto stat = Stat::stat(path);
    if (stat) {
      return {path, stat, level};
    }
  }

  const auto shallowest_path =
    get_path_in_cache(k_min_cache_levels, key_string);
  return {shallowest_path, Stat(), k_min_cache_levels};
}

void
LocalStorage::clean_internal_tempdir()
{
  MTR_SCOPE("local_storage", "clean_internal_tempdir");

  const auto now = util::TimePoint::now();
  const auto cleaned_stamp = FMT("{}/.cleaned", m_config.temporary_dir());
  const auto cleaned_stat = Stat::stat(cleaned_stamp);
  if (cleaned_stat
      && cleaned_stat.mtime() + k_tempdir_cleanup_interval >= now) {
    // No cleanup needed.
    return;
  }

  LOG("Cleaning up {}", m_config.temporary_dir());
  Util::ensure_dir_exists(m_config.temporary_dir());
  Util::traverse(m_config.temporary_dir(),
                 [now](const std::string& path, bool is_dir) {
                   if (is_dir) {
                     return;
                   }
                   const auto st = Stat::lstat(path, Stat::OnError::log);
                   if (st && st.mtime() + k_tempdir_cleanup_interval < now) {
                     Util::unlink_tmp(path);
                   }
                 });

  util::write_file(cleaned_stamp, "");
}

std::optional<core::StatisticsCounters>
LocalStorage::update_stats_and_maybe_move_cache_file(
  const Digest& key,
  const std::string& current_path,
  const core::StatisticsCounters& counter_updates,
  const core::CacheEntryType type)
{
  if (counter_updates.all_zero()) {
    return std::nullopt;
  }

  // Use stats file in the level one subdirectory for cache bookkeeping counters
  // since cleanup is performed on level one. Use stats file in the level two
  // subdirectory for other counters to reduce lock contention.
  const bool use_stats_on_level_1 =
    counter_updates.get(Statistic::cache_size_kibibyte) != 0
    || counter_updates.get(Statistic::files_in_cache) != 0;
  std::string level_string = FMT("{:x}", key.bytes()[0] >> 4);
  if (!use_stats_on_level_1) {
    level_string += FMT("/{:x}", key.bytes()[0] & 0xF);
  }

  const auto stats_file =
    FMT("{}/{}/stats", m_config.cache_dir(), level_string);
  auto counters = StatsFile(stats_file).update([&counter_updates](auto& cs) {
    cs.increment(counter_updates);
  });
  if (!counters) {
    return std::nullopt;
  }

  if (use_stats_on_level_1) {
    // Only consider moving the cache file to another level when we have read
    // the level 1 stats file since it's only then we know the proper
    // files_in_cache value.
    const auto wanted_level =
      calculate_wanted_cache_level(counters->get(Statistic::files_in_cache));
    const auto wanted_path =
      get_path_in_cache(wanted_level, key.to_string() + suffix_from_type(type));
    if (current_path != wanted_path) {
      Util::ensure_dir_exists(Util::dir_name(wanted_path));
      LOG("Moving {} to {}", current_path, wanted_path);
      try {
        Util::rename(current_path, wanted_path);
      } catch (const core::Error&) {
        // Two ccache processes may move the file at the same time, so failure
        // to rename is OK.
      }
      for (const auto& raw_file : m_added_raw_files) {
        try {
          Util::rename(raw_file,
                       FMT("{}/{}",
                           Util::dir_name(wanted_path),
                           Util::base_name(raw_file)));
        } catch (const core::Error&) {
          // Two ccache processes may move the file at the same time, so failure
          // to rename is OK.
        }
      }
    }
  }
  return counters;
}

std::string
LocalStorage::get_path_in_cache(const uint8_t level,
                                const std::string_view name) const
{
  ASSERT(level >= 1 && level <= 8);
  ASSERT(name.length() >= level);

  std::string path(m_config.cache_dir());
  path.reserve(path.size() + level * 2 + 1 + name.length() - level);

  for (uint8_t i = 0; i < level; ++i) {
    path.push_back('/');
    path.push_back(name.at(i));
  }

  path.push_back('/');
  const std::string_view name_remaining = name.substr(level);
  path.append(name_remaining.data(), name_remaining.length());

  return path;
}

} // namespace storage::local