// Copyright Epic Games, Inc. All Rights Reserved.

#include <zenstore/gc.h>

#include <zencore/compactbinary.h>
#include <zencore/compactbinarybuilder.h>
#include <zencore/compactbinaryvalidation.h>
#include <zencore/except.h>
#include <zencore/filesystem.h>
#include <zencore/fmtutils.h>
#include <zencore/logging.h>
#include <zencore/scopeguard.h>
#include <zencore/string.h>
#include <zencore/testing.h>
#include <zencore/testutils.h>
#include <zencore/timer.h>
#include <zencore/trace.h>
#include <zencore/workthreadpool.h>
#include <zenstore/cidstore.h>
#include <zenstore/scrubcontext.h>

#include "cas.h"

#include <fmt/format.h>
#include <filesystem>

#if ZEN_PLATFORM_WINDOWS
#	include <zencore/windows.h>
#else
#	include <fcntl.h>
#	include <sys/file.h>
#	include <sys/stat.h>
#	include <unistd.h>
#endif

#if ZEN_WITH_TESTS
#	include <zencore/compress.h>
#	include <algorithm>
#	include <random>
#endif

template<>
struct fmt::formatter<zen::GcClock::TimePoint> : formatter<string_view>
{
	template<typename FormatContext>
	auto format(const zen::GcClock::TimePoint& TimePoint, FormatContext& ctx)
	{
		std::time_t						 Time = std::chrono::system_clock::to_time_t(TimePoint);
		zen::ExtendableStringBuilder<32> String;
		String << std::ctime(&Time);
		return formatter<string_view>::format(String.ToView(), ctx);
	}
};

namespace zen {

using namespace std::literals;
namespace fs = std::filesystem;

//////////////////////////////////////////////////////////////////////////

namespace {
	std::error_code CreateGCReserve(const std::filesystem::path& Path, uint64_t Size)
	{
		if (Size == 0)
		{
			std::filesystem::remove(Path);
			return std::error_code{};
		}
		CreateDirectories(Path.parent_path());
		if (std::filesystem::is_regular_file(Path) && std::filesystem::file_size(Path) == Size)
		{
			return std::error_code();
		}
#if ZEN_PLATFORM_WINDOWS
		DWORD dwCreationDisposition = CREATE_ALWAYS;
		DWORD dwDesiredAccess		= GENERIC_READ | GENERIC_WRITE;

		const DWORD dwShareMode			 = 0;
		const DWORD dwFlagsAndAttributes = FILE_ATTRIBUTE_NORMAL;
		HANDLE		hTemplateFile		 = nullptr;

		HANDLE FileHandle = CreateFile(Path.c_str(),
									   dwDesiredAccess,
									   dwShareMode,
									   /* lpSecurityAttributes */ nullptr,
									   dwCreationDisposition,
									   dwFlagsAndAttributes,
									   hTemplateFile);

		if (FileHandle == INVALID_HANDLE_VALUE)
		{
			return MakeErrorCodeFromLastError();
		}
		bool		  Keep = true;
		auto		  _	   = MakeGuard([&]() {
			::CloseHandle(FileHandle);
			if (!Keep)
			{
				::DeleteFile(Path.c_str());
			}
		});
		LARGE_INTEGER liFileSize;
		liFileSize.QuadPart = Size;
		BOOL OK				= ::SetFilePointerEx(FileHandle, liFileSize, 0, FILE_BEGIN);
		if (!OK)
		{
			return MakeErrorCodeFromLastError();
		}
		OK = ::SetEndOfFile(FileHandle);
		if (!OK)
		{
			return MakeErrorCodeFromLastError();
		}
		Keep = true;
#else
		int OpenFlags = O_CLOEXEC | O_RDWR | O_CREAT;
		int Fd		  = open(Path.c_str(), OpenFlags, 0666);
		if (Fd < 0)
		{
			return MakeErrorCodeFromLastError();
		}

		bool Keep = true;
		auto _	  = MakeGuard([&]() {
			   close(Fd);
			   if (!Keep)
			   {
				   unlink(Path.c_str());
			   }
		   });

		if (fchmod(Fd, 0666) < 0)
		{
			return MakeErrorCodeFromLastError();
		}

#	if ZEN_PLATFORM_MAC
		if (ftruncate(Fd, (off_t)Size) < 0)
		{
			return MakeErrorCodeFromLastError();
		}
#	else
		if (ftruncate64(Fd, (off64_t)Size) < 0)
		{
			return MakeErrorCodeFromLastError();
		}
		int Error = posix_fallocate64(Fd, 0, (off64_t)Size);
		if (Error)
		{
			return MakeErrorCode(Error);
		}
#	endif
		Keep = true;
#endif
		return std::error_code{};
	}

}  // namespace

//////////////////////////////////////////////////////////////////////////

CbObject
LoadCompactBinaryObject(const fs::path& Path)
{
	FileContents Result = ReadFile(Path);

	if (!Result.ErrorCode)
	{
		IoBuffer Buffer = Result.Flatten();
		if (CbValidateError Error = ValidateCompactBinary(Buffer, CbValidateMode::All); Error == CbValidateError::None)
		{
			return LoadCompactBinaryObject(Buffer);
		}
	}

	return CbObject();
}

void
SaveCompactBinaryObject(const fs::path& Path, const CbObject& Object)
{
	WriteFile(Path, Object.GetBuffer().AsIoBuffer());
}

//////////////////////////////////////////////////////////////////////////

struct GcContext::GcState
{
	using CacheKeyContexts = std::unordered_map<std::string, std::vector<IoHash>>;

	CacheKeyContexts   m_ExpiredCacheKeys;
	HashKeySet		   m_RetainedCids;
	HashKeySet		   m_DeletedCids;
	GcClock::TimePoint m_CacheExpireTime;
	GcClock::TimePoint m_ProjectStoreExpireTime;
	bool			   m_DeletionMode		 = true;
	bool			   m_CollectSmallObjects = false;
	bool			   m_SkipCid			 = false;

	std::filesystem::path DiskReservePath;
};

GcContext::GcContext(const GcClock::TimePoint& CacheExpireTime, const GcClock::TimePoint& ProjectStoreExpireTime)
: m_State(std::make_unique<GcState>())
{
	m_State->m_CacheExpireTime		  = CacheExpireTime;
	m_State->m_ProjectStoreExpireTime = ProjectStoreExpireTime;
}

GcContext::~GcContext()
{
}

void
GcContext::AddRetainedCids(std::span<const IoHash> Cids)
{
	m_State->m_RetainedCids.AddHashesToSet(Cids);
}

void
GcContext::SetExpiredCacheKeys(const std::string& CacheKeyContext, std::vector<IoHash>&& ExpiredKeys)
{
	m_State->m_ExpiredCacheKeys[CacheKeyContext] = std::move(ExpiredKeys);
}

void
GcContext::IterateCids(std::function<void(const IoHash&)> Callback)
{
	m_State->m_RetainedCids.IterateHashes([&](const IoHash& Hash) { Callback(Hash); });
}

void
GcContext::FilterCids(std::span<const IoHash> Cid, std::function<void(const IoHash&)> KeepFunc)
{
	m_State->m_RetainedCids.FilterHashes(Cid, [&](const IoHash& Hash) { KeepFunc(Hash); });
}

void
GcContext::FilterCids(std::span<const IoHash> Cid, std::function<void(const IoHash&, bool)>&& FilterFunc)
{
	m_State->m_RetainedCids.FilterHashes(Cid, std::move(FilterFunc));
}

void
GcContext::AddDeletedCids(std::span<const IoHash> Cas)
{
	m_State->m_DeletedCids.AddHashesToSet(Cas);
}

const HashKeySet&
GcContext::DeletedCids()
{
	return m_State->m_DeletedCids;
}

std::span<const IoHash>
GcContext::ExpiredCacheKeys(const std::string& CacheKeyContext) const
{
	return m_State->m_ExpiredCacheKeys[CacheKeyContext];
}

bool
GcContext::SkipCid() const
{
	return m_State->m_SkipCid;
}

void
GcContext::SetSkipCid(bool NewState)
{
	m_State->m_SkipCid = NewState;
}

bool
GcContext::IsDeletionMode() const
{
	return m_State->m_DeletionMode;
}

void
GcContext::SetDeletionMode(bool NewState)
{
	m_State->m_DeletionMode = NewState;
}

bool
GcContext::CollectSmallObjects() const
{
	return m_State->m_CollectSmallObjects;
}

void
GcContext::CollectSmallObjects(bool NewState)
{
	m_State->m_CollectSmallObjects = NewState;
}

GcClock::TimePoint
GcContext::CacheExpireTime() const
{
	return m_State->m_CacheExpireTime;
}

GcClock::TimePoint
GcContext::ProjectStoreExpireTime() const
{
	return m_State->m_ProjectStoreExpireTime;
}

void
GcContext::DiskReservePath(const std::filesystem::path& Path)
{
	m_State->DiskReservePath = Path;
}

uint64_t
GcContext::ClaimGCReserve()
{
	if (!std::filesystem::is_regular_file(m_State->DiskReservePath))
	{
		return 0;
	}
	uint64_t ReclaimedSize = std::filesystem::file_size(m_State->DiskReservePath);
	if (std::filesystem::remove(m_State->DiskReservePath))
	{
		return ReclaimedSize;
	}
	return 0;
}

//////////////////////////////////////////////////////////////////////////

GcContributor::GcContributor(GcManager& Gc) : m_Gc(Gc)
{
	m_Gc.AddGcContributor(this);
}

GcContributor::~GcContributor()
{
	m_Gc.RemoveGcContributor(this);
}

//////////////////////////////////////////////////////////////////////////

GcStorage::GcStorage(GcManager& Gc) : m_Gc(Gc)
{
	m_Gc.AddGcStorage(this);
}

GcStorage::~GcStorage()
{
	m_Gc.RemoveGcStorage(this);
}

//////////////////////////////////////////////////////////////////////////

GcManager::GcManager() : m_Log(logging::Get("gc"))
{
}

GcManager::~GcManager()
{
}

void
GcManager::AddGcContributor(GcContributor* Contributor)
{
	RwLock::ExclusiveLockScope _(m_Lock);
	m_GcContribs.push_back(Contributor);
}

void
GcManager::RemoveGcContributor(GcContributor* Contributor)
{
	RwLock::ExclusiveLockScope _(m_Lock);
	std::erase_if(m_GcContribs, [&](GcContributor* $) { return $ == Contributor; });
}

void
GcManager::AddGcStorage(GcStorage* Storage)
{
	ZEN_ASSERT(Storage != nullptr);
	RwLock::ExclusiveLockScope _(m_Lock);
	m_GcStorage.push_back(Storage);
}

void
GcManager::RemoveGcStorage(GcStorage* Storage)
{
	RwLock::ExclusiveLockScope _(m_Lock);
	std::erase_if(m_GcStorage, [&](GcStorage* $) { return $ == Storage; });
}

void
GcManager::ScrubStorage(ScrubContext& GcCtx)
{
	RwLock::SharedLockScope _(m_Lock);

	for (GcStorage* Storage : m_GcStorage)
	{
		Storage->ScrubStorage(GcCtx);
	}
}

void
GcManager::CollectGarbage(GcContext& GcCtx)
{
	ZEN_TRACE_CPU("Gc::CollectGarbage");

	RwLock::SharedLockScope _(m_Lock);

	// First gather reference set
	{
		ZEN_TRACE_CPU("Gc::CollectGarbage::GatherReferences");
		Stopwatch  Timer;
		const auto Guard = MakeGuard([&] { ZEN_INFO("gathered references in {}", NiceTimeSpanMs(Timer.GetElapsedTimeMs())); });
		for (GcContributor* Contributor : m_GcContribs)
		{
			Contributor->GatherReferences(GcCtx);
		}
	}

	// Then trim storage
	{
		ZEN_TRACE_CPU("Gc::CollectGarbage::CollectGarbage");

		GcStorageSize GCTotalSizeDiff;
		Stopwatch	  Timer;
		const auto	  Guard = MakeGuard([&] {
			   ZEN_INFO("collected garbage in {}. Removed {} disk space, {} memory",
						NiceTimeSpanMs(Timer.GetElapsedTimeMs()),
						NiceBytes(GCTotalSizeDiff.DiskSize),
						NiceBytes(GCTotalSizeDiff.MemorySize));
		   });
		for (GcStorage* Storage : m_GcStorage)
		{
			const auto PreSize = Storage->StorageSize();
			Storage->CollectGarbage(GcCtx);
			const auto PostSize = Storage->StorageSize();
			GCTotalSizeDiff.DiskSize += PreSize.DiskSize > PostSize.DiskSize ? PreSize.DiskSize - PostSize.DiskSize : 0;
			GCTotalSizeDiff.MemorySize += PreSize.MemorySize > PostSize.MemorySize ? PreSize.MemorySize - PostSize.MemorySize : 0;
		}
	}
}

GcStorageSize
GcManager::TotalStorageSize() const
{
	ZEN_TRACE_CPU("Gc::TotalStorageSize");

	RwLock::SharedLockScope _(m_Lock);

	GcStorageSize TotalSize;

	for (GcStorage* Storage : m_GcStorage)
	{
		const auto Size = Storage->StorageSize();
		TotalSize.DiskSize += Size.DiskSize;
		TotalSize.MemorySize += Size.MemorySize;
	}

	return TotalSize;
}

//////////////////////////////////////////////////////////////////////////

void
DiskUsageWindow::KeepRange(GcClock::Tick StartTick, GcClock::Tick EndTick)
{
	auto It = m_LogWindow.begin();
	if (It == m_LogWindow.end())
	{
		return;
	}
	while (It->SampleTime < StartTick)
	{
		++It;
		if (It == m_LogWindow.end())
		{
			m_LogWindow.clear();
			return;
		}
	}
	m_LogWindow.erase(m_LogWindow.begin(), It);

	It = m_LogWindow.begin();
	while (It != m_LogWindow.end())
	{
		if (It->SampleTime >= EndTick)
		{
			m_LogWindow.erase(It, m_LogWindow.end());
			return;
		}
		It++;
	}
}

std::vector<uint64_t>
DiskUsageWindow::GetDiskDeltas(GcClock::Tick StartTick, GcClock::Tick EndTick, GcClock::Tick DeltaWidth, uint64_t& OutMaxDelta) const
{
	ZEN_ASSERT(StartTick != -1);
	ZEN_ASSERT(DeltaWidth > 0);

	std::vector<uint64_t> Result;
	Result.reserve((EndTick - StartTick + DeltaWidth - 1) / DeltaWidth);

	size_t		  WindowSize	  = m_LogWindow.size();
	GcClock::Tick FirstWindowTick = WindowSize < 2 ? EndTick : m_LogWindow[1].SampleTime;

	GcClock::Tick RangeStart = StartTick;
	while (FirstWindowTick >= RangeStart + DeltaWidth && RangeStart < EndTick)
	{
		Result.push_back(0);
		RangeStart += DeltaWidth;
	}

	uint64_t DeltaSum	 = 0;
	size_t	 WindowIndex = 1;
	while (WindowIndex < WindowSize && RangeStart < EndTick)
	{
		const DiskUsageEntry& Entry = m_LogWindow[WindowIndex];
		if (Entry.SampleTime < RangeStart)
		{
			++WindowIndex;
			continue;
		}
		GcClock::Tick RangeEnd = Min(EndTick, RangeStart + DeltaWidth);
		ZEN_ASSERT(Entry.SampleTime >= RangeStart);
		if (Entry.SampleTime >= RangeEnd)
		{
			Result.push_back(DeltaSum);
			OutMaxDelta = Max(DeltaSum, OutMaxDelta);
			DeltaSum	= 0;
			RangeStart	= RangeEnd;
			continue;
		}
		const DiskUsageEntry& PrevEntry = m_LogWindow[WindowIndex - 1];
		if (Entry.DiskUsage > PrevEntry.DiskUsage)
		{
			uint64_t Delta = Entry.DiskUsage - PrevEntry.DiskUsage;
			DeltaSum += Delta;
		}
		WindowIndex++;
	}

	while (RangeStart < EndTick)
	{
		Result.push_back(DeltaSum);
		OutMaxDelta = Max(DeltaSum, OutMaxDelta);
		DeltaSum	= 0;
		RangeStart += DeltaWidth;
	}
	return Result;
}

GcClock::Tick
DiskUsageWindow::FindTimepointThatRemoves(uint64_t Amount, GcClock::Tick EndTick) const
{
	ZEN_ASSERT(Amount > 0);
	uint64_t RemainingToFind = Amount;
	size_t	 Offset			 = 1;
	while (Offset < m_LogWindow.size())
	{
		const DiskUsageEntry& Entry = m_LogWindow[Offset];
		if (Entry.SampleTime >= EndTick)
		{
			return EndTick;
		}
		const DiskUsageEntry& PreviousEntry = m_LogWindow[Offset - 1];
		uint64_t			  Delta			= Entry.DiskUsage > PreviousEntry.DiskUsage ? Entry.DiskUsage - PreviousEntry.DiskUsage : 0;
		if (Delta >= RemainingToFind)
		{
			return m_LogWindow[Offset].SampleTime + 1;
		}
		RemainingToFind -= Delta;
		Offset++;
	}
	return EndTick;
}

//////////////////////////////////////////////////////////////////////////

GcScheduler::GcScheduler(GcManager& GcManager) : m_Log(logging::Get("gc")), m_GcManager(GcManager)
{
	m_GcManager.SetDiskWriteBlocker(this);
}

GcScheduler::~GcScheduler()
{
	m_GcManager.SetDiskWriteBlocker(nullptr);
	Shutdown();
}

void
GcScheduler::Initialize(const GcSchedulerConfig& Config)
{
	using namespace std::chrono;

	m_Config = Config;

	if (m_Config.Interval.count() && m_Config.Interval < m_Config.MonitorInterval)
	{
		m_Config.Interval = m_Config.MonitorInterval;
	}

	if (m_Config.LightweightInterval.count() && m_Config.LightweightInterval < m_Config.MonitorInterval)
	{
		m_Config.LightweightInterval = m_Config.MonitorInterval;
	}

	std::filesystem::create_directories(Config.RootDirectory);

	std::error_code Ec = CreateGCReserve(m_Config.RootDirectory / "reserve.gc", m_Config.DiskReserveSize);
	if (Ec)
	{
		ZEN_WARN("unable to create GC reserve at '{}' with size {}, reason '{}'",
				 m_Config.RootDirectory / "reserve.gc",
				 NiceBytes(m_Config.DiskReserveSize),
				 Ec.message());
	}

	CheckDiskSpace();

	m_LastGcTime			= GcClock::Now();
	m_LastLightweightGcTime = m_LastGcTime;
	m_LastGcExpireTime		= GcClock::TimePoint::min();

	if (CbObject SchedulerState = LoadCompactBinaryObject(Config.RootDirectory / "gc_state"))
	{
		m_LastGcTime = GcClock::TimePoint(GcClock::Duration(SchedulerState["LastGcTime"sv].AsInt64()));
		m_LastGcExpireTime =
			GcClock::TimePoint(GcClock::Duration(SchedulerState["LastGcExpireTime"].AsInt64(GcClock::Duration::min().count())));
		if (m_LastGcTime + m_Config.Interval < GcClock::Now())
		{
			// TODO: Trigger GC?
			m_LastGcTime			= GcClock::Now();
			m_LastLightweightGcTime = m_LastGcTime;
		}
	}

	m_DiskUsageLog.Open(m_Config.RootDirectory / "gc.dlog", CasLogFile::Mode::kWrite);
	m_DiskUsageLog.Initialize();
	const GcClock::Tick LastGCTick = m_LastGcTime.time_since_epoch().count();
	m_DiskUsageLog.Replay(
		[this, LastGCTick](const DiskUsageWindow::DiskUsageEntry& Entry) {
			if (Entry.SampleTime >= m_LastGcExpireTime.time_since_epoch().count())
			{
				m_DiskUsageWindow.Append(Entry);
			}
		},
		0);

	m_GcThread = std::thread(&GcScheduler::SchedulerThread, this);
}

void
GcScheduler::Shutdown()
{
	if (static_cast<uint32_t>(GcSchedulerStatus::kStopped) != m_Status)
	{
		bool GcIsRunning = m_Status == static_cast<uint32_t>(GcSchedulerStatus::kRunning);
		m_Status		 = static_cast<uint32_t>(GcSchedulerStatus::kStopped);
		m_GcSignal.notify_one();

		if (m_GcThread.joinable())
		{
			if (GcIsRunning)
			{
				ZEN_INFO("Waiting for garbage collection to complete");
			}
			m_GcThread.join();
		}
	}
	m_DiskUsageLog.Flush();
	m_DiskUsageLog.Close();
}

bool
GcScheduler::TriggerGc(const GcScheduler::TriggerGcParams& Params)
{
	if (m_Config.Enabled)
	{
		std::unique_lock Lock(m_GcMutex);
		if (static_cast<uint32_t>(GcSchedulerStatus::kIdle) == m_Status)
		{
			m_TriggerGcParams  = Params;
			uint32_t IdleState = static_cast<uint32_t>(GcSchedulerStatus::kIdle);

			if (m_Status.compare_exchange_strong(/* expected */ IdleState,
												 /* desired */ static_cast<uint32_t>(GcSchedulerStatus::kRunning)))
			{
				m_GcSignal.notify_one();
				return true;
			}
		}
	}

	return false;
}

bool
GcScheduler::TriggerScrub(const TriggerScrubParams& Params)
{
	std::unique_lock Lock(m_GcMutex);

	if (static_cast<uint32_t>(GcSchedulerStatus::kIdle) == m_Status)
	{
		m_TriggerScrubParams = Params;
		uint32_t IdleState	 = static_cast<uint32_t>(GcSchedulerStatus::kIdle);

		if (m_Status.compare_exchange_strong(/* expected */ IdleState, /* desired */ static_cast<uint32_t>(GcSchedulerStatus::kRunning)))
		{
			m_GcSignal.notify_one();

			return true;
		}
	}

	return false;
}

DiskSpace
GcScheduler::CheckDiskSpace()
{
	std::error_code Ec;
	DiskSpace		Space = DiskSpaceInfo(m_Config.RootDirectory, Ec);
	if (Ec)
	{
		m_AreDiskWritesBlocked.store(true);
		ZEN_WARN("get disk space info for path '{}' FAILED, reason: '{}'", m_Config.RootDirectory, Ec.message());
		return {0, 0};
	}

	bool AreDiskWritesBlocked = m_AreDiskWritesBlocked;
	bool IsLowOnDiskSpace = (m_Config.MinimumFreeDiskSpaceToAllowWrites) != 0 && (Space.Free < m_Config.MinimumFreeDiskSpaceToAllowWrites);
	if (IsLowOnDiskSpace != AreDiskWritesBlocked)
	{
		m_AreDiskWritesBlocked.store(IsLowOnDiskSpace);
		if (IsLowOnDiskSpace)
		{
			ZEN_WARN("Writing to disk is blocked, free disk space: {}, minimum required {}",
					 NiceBytes(Space.Free),
					 NiceBytes(m_Config.MinimumFreeDiskSpaceToAllowWrites));
		}
		else
		{
			ZEN_INFO("Writing to disk is unblocked, free disk space: {}, minimum required {}",
					 NiceBytes(Space.Free),
					 NiceBytes(m_Config.MinimumFreeDiskSpaceToAllowWrites));
		}
	}
	return Space;
}

void
GcScheduler::SchedulerThread()
{
	SetCurrentThreadName("GcScheduler");

	std::chrono::seconds WaitTime{0};

	for (;;)
	{
		bool Timeout = false;
		{
			ZEN_ASSERT(WaitTime.count() >= 0);
			std::unique_lock Lock(m_GcMutex);
			Timeout = std::cv_status::timeout == m_GcSignal.wait_for(Lock, WaitTime);
		}

		if (Status() == GcSchedulerStatus::kStopped)
		{
			break;
		}

		if (!m_Config.Enabled && !m_TriggerScrubParams)
		{
			WaitTime = std::chrono::seconds::max();
			continue;
		}

		if (!Timeout && Status() == GcSchedulerStatus::kIdle)
		{
			continue;
		}

		try
		{
			bool				 DoGc					 = m_Config.Enabled;
			bool				 DoScrubbing			 = false;
			std::chrono::seconds ScrubTimeslice			 = std::chrono::seconds::max();
			bool				 DoDelete				 = true;
			bool				 CollectSmallObjects	 = m_Config.CollectSmallObjects;
			std::chrono::seconds GcInterval				 = m_Config.Interval;
			std::chrono::seconds LightwightGcInterval	 = m_Config.LightweightInterval;
			std::chrono::seconds MaxCacheDuration		 = m_Config.MaxCacheDuration;
			std::chrono::seconds MaxProjectStoreDuration = m_Config.MaxProjectStoreDuration;
			uint64_t			 DiskSizeSoftLimit		 = m_Config.DiskSizeSoftLimit;
			bool				 SkipCid				 = false;

			bool DiskSpaceGCTriggered = false;
			bool TimeBasedGCTriggered = false;

			GcClock::TimePoint Now = GcClock::Now();

			if (m_TriggerGcParams)
			{
				const auto TriggerParams = m_TriggerGcParams.value();
				m_TriggerGcParams.reset();

				CollectSmallObjects = TriggerParams.CollectSmallObjects;

				if (TriggerParams.MaxCacheDuration != std::chrono::seconds::max())
				{
					MaxCacheDuration = TriggerParams.MaxCacheDuration;
				}
				if (TriggerParams.MaxProjectStoreDuration != std::chrono::seconds::max())
				{
					MaxProjectStoreDuration = TriggerParams.MaxProjectStoreDuration;
				}
				if (TriggerParams.DiskSizeSoftLimit != 0)
				{
					DiskSizeSoftLimit = TriggerParams.DiskSizeSoftLimit;
				}
				if (TriggerParams.SkipCid)
				{
					SkipCid = true;
				}
			}

			if (m_TriggerScrubParams)
			{
				DoScrubbing = true;

				if (m_TriggerScrubParams->SkipGc)
				{
					DoGc = false;
				}

				ScrubTimeslice = m_TriggerScrubParams->MaxTimeslice;
			}

			if (DoScrubbing)
			{
				ScrubStorage(DoDelete, ScrubTimeslice);
				m_TriggerScrubParams.reset();
			}

			if (!DoGc)
			{
				continue;
			}

			GcClock::TimePoint CacheExpireTime =
				MaxCacheDuration == GcClock::Duration::max() ? GcClock::TimePoint::min() : Now - MaxCacheDuration;
			GcClock::TimePoint ProjectStoreExpireTime =
				MaxProjectStoreDuration == GcClock::Duration::max() ? GcClock::TimePoint::min() : Now - MaxProjectStoreDuration;

			const GcStorageSize TotalSize = m_GcManager.TotalStorageSize();

			if (Timeout && Status() == GcSchedulerStatus::kIdle)
			{
				DiskSpace Space = CheckDiskSpace();

				const int64_t				PressureGraphLength = 30;
				const std::chrono::duration LoadGraphTime		= PressureGraphLength * m_Config.MonitorInterval;
				std::vector<uint64_t>		DiskDeltas;
				uint64_t					MaxLoad = 0;

				{
					const GcClock::Tick EpochTickCount = GcClock::Now().time_since_epoch().count();
					std::unique_lock	Lock(m_GcMutex);
					if (AreDiskWritesAllowed())
					{
						m_DiskUsageLog.Append({.SampleTime = EpochTickCount, .DiskUsage = TotalSize.DiskSize});
					}
					m_DiskUsageWindow.Append({.SampleTime = EpochTickCount, .DiskUsage = TotalSize.DiskSize});
					const GcClock::TimePoint LoadGraphStartTime = Now - LoadGraphTime;
					const GcClock::Tick		 Start				= LoadGraphStartTime.time_since_epoch().count();
					const GcClock::Tick		 End				= Now.time_since_epoch().count();
					DiskDeltas									= m_DiskUsageWindow.GetDiskDeltas(Start,
																  End,
																  Max(1, (End - Start + PressureGraphLength - 1) / PressureGraphLength),
																  MaxLoad);
				}

				std::string LoadGraph;
				LoadGraph.resize(DiskDeltas.size(), '0');
				if (DiskDeltas.size() > 0 && MaxLoad > 0)
				{
					static const char LoadIndicator[11] = "0123456789";
					for (size_t Index = 0; Index < DiskDeltas.size(); ++Index)
					{
						size_t LoadIndex = (9 * DiskDeltas[Index] + MaxLoad - 1) / MaxLoad;
						LoadGraph[Index] = LoadIndicator[LoadIndex];
					}
				}

				uint64_t GcDiskSpaceGoal = 0;
				if (DiskSizeSoftLimit != 0 && TotalSize.DiskSize > DiskSizeSoftLimit)
				{
					GcDiskSpaceGoal = TotalSize.DiskSize - DiskSizeSoftLimit;
					std::unique_lock Lock(m_GcMutex);
					GcClock::Tick	 AgeTick = m_DiskUsageWindow.FindTimepointThatRemoves(GcDiskSpaceGoal, Now.time_since_epoch().count());
					GcClock::TimePoint SizeBasedExpireTime = GcClock::TimePointFromTick(AgeTick);
					if (SizeBasedExpireTime > CacheExpireTime)
					{
						CacheExpireTime = SizeBasedExpireTime;
					}
					if (SizeBasedExpireTime > ProjectStoreExpireTime)
					{
						ProjectStoreExpireTime = SizeBasedExpireTime;
					}
				}

				std::chrono::seconds RemaingTimeUntilGc =
					GcInterval.count() == 0 ? std::chrono::seconds::max()
											: std::chrono::duration_cast<std::chrono::seconds>(m_LastGcTime + GcInterval - GcClock::Now());
				if (RemaingTimeUntilGc < std::chrono::seconds::zero())
				{
					RemaingTimeUntilGc = std::chrono::seconds::zero();
				}
				std::chrono::seconds RemaingTimeUntilLightweightGc =
					LightwightGcInterval.count() == 0
						? std::chrono::seconds::max()
						: std::chrono::duration_cast<std::chrono::seconds>(m_LastLightweightGcTime + LightwightGcInterval - GcClock::Now());
				if (RemaingTimeUntilLightweightGc < std::chrono::seconds::zero())
				{
					RemaingTimeUntilLightweightGc = std::chrono::seconds::zero();
				}

				if (GcDiskSpaceGoal > 0)
				{
					DiskSpaceGCTriggered = true;
				}
				else if (RemaingTimeUntilGc.count() == 0)
				{
					TimeBasedGCTriggered = true;
				}
				else if (RemaingTimeUntilLightweightGc.count() == 0)
				{
					TimeBasedGCTriggered = true;
					SkipCid				 = true;
				}

				std::string NextTriggerStatus;
				if (GcInterval.count() != 0 || LightwightGcInterval.count() != 0 || DiskSizeSoftLimit != 0)
				{
					ExtendableStringBuilder<256> Sb;
					if (DiskSpaceGCTriggered)
					{
						Sb.Append(fmt::format(" Disk space exceeds {}, trying to reclaim {}.",
											  NiceBytes(DiskSizeSoftLimit),
											  NiceBytes(GcDiskSpaceGoal)));
					}
					else if (TimeBasedGCTriggered)
					{
						if (SkipCid)
						{
							Sb.Append(fmt::format(" Lightweight GC schedule triggered."));
						}
						else
						{
							Sb.Append(fmt::format(" GC schedule triggered."));
						}
					}
					else
					{
						if (GcInterval.count() != 0)
						{
							Sb.Append(fmt::format(" Full GC in {}.",
												  NiceTimeSpanMs(uint64_t(std::chrono::milliseconds(RemaingTimeUntilGc).count()))));
						}
						if (LightwightGcInterval.count() != 0)
						{
							Sb.Append(
								fmt::format(" Lightweight GC in {}.",
											NiceTimeSpanMs(uint64_t(std::chrono::milliseconds(RemaingTimeUntilLightweightGc).count()))));
						}
						if (DiskSizeSoftLimit != 0 && DiskSizeSoftLimit > TotalSize.DiskSize)
						{
							Sb.Append(fmt::format(" Disk usagage GC in {}.", NiceBytes(DiskSizeSoftLimit - TotalSize.DiskSize)));
						}
					}
					NextTriggerStatus = Sb;
				}

				ZEN_INFO(
					"{} used{}. '{}': {} in use, {} free. Disk writes last {} per {} [{}], peak {}/s.{}",
					NiceBytes(TotalSize.DiskSize),
					DiskSizeSoftLimit == 0 ? "" : fmt::format(", {} soft limit", NiceBytes(DiskSizeSoftLimit)),
					m_Config.RootDirectory,
					NiceBytes(Space.Free),
					NiceBytes(Space.Total),
					NiceTimeSpanMs(uint64_t(std::chrono::milliseconds(LoadGraphTime).count())),
					NiceTimeSpanMs(uint64_t(std::chrono::milliseconds(LoadGraphTime).count() / PressureGraphLength)),
					LoadGraph,
					NiceBytes(MaxLoad * uint64_t(std::chrono::seconds(1).count()) / uint64_t(std::chrono::seconds(LoadGraphTime).count())),
					NextTriggerStatus);

				if (!DiskSpaceGCTriggered && !TimeBasedGCTriggered)
				{
					WaitTime = m_Config.MonitorInterval;
					if (RemaingTimeUntilGc < WaitTime)
					{
						WaitTime = RemaingTimeUntilGc;
					}
					if (RemaingTimeUntilLightweightGc < WaitTime)
					{
						WaitTime = RemaingTimeUntilLightweightGc;
					}
					continue;
				}

				uint32_t IdleState = static_cast<uint32_t>(GcSchedulerStatus::kIdle);
				if (!m_Status.compare_exchange_strong(IdleState, static_cast<uint32_t>(GcSchedulerStatus::kRunning)))
				{
					WaitTime = m_Config.MonitorInterval;
					continue;
				}
			}

			CollectGarbage(CacheExpireTime, ProjectStoreExpireTime, DoDelete, CollectSmallObjects, SkipCid);

			uint32_t RunningState = static_cast<uint32_t>(GcSchedulerStatus::kRunning);
			if (!m_Status.compare_exchange_strong(RunningState, static_cast<uint32_t>(GcSchedulerStatus::kIdle)))
			{
				ZEN_ASSERT(m_Status == static_cast<uint32_t>(GcSchedulerStatus::kStopped));
				break;
			}

			WaitTime = std::chrono::seconds(0);
		}
		catch (std::system_error& SystemError)
		{
			if (IsOOM(SystemError.code()))
			{
				ZEN_WARN("scheduling garbage collection ran out of memory: '{}'", SystemError.what());
			}
			else if (IsOOD(SystemError.code()))
			{
				ZEN_WARN("scheduling garbage collection ran out of disk space: '{}'", SystemError.what());
			}
			else
			{
				ZEN_ERROR("scheduling garbage collection failed with system error exception: '{}'", SystemError.what());
			}
		}
		catch (std::bad_alloc& BadAlloc)
		{
			ZEN_WARN("scheduling garbage collection ran out of memory: '{}'", BadAlloc.what());
		}
		catch (std::exception& Ex)
		{
			ZEN_ERROR("scheduling garbage collection failed with: '{}'", Ex.what());
			WaitTime = m_Config.MonitorInterval;
		}
	}
}

void
GcScheduler::ScrubStorage(bool DoDelete, std::chrono::seconds TimeSlice)
{
	const std::chrono::steady_clock::time_point TimeNow	 = std::chrono::steady_clock::now();
	std::chrono::steady_clock::time_point		Deadline = TimeNow + TimeSlice;
	// there really should be a saturating add in std::chrono
	if (Deadline < TimeNow)
	{
		Deadline = std::chrono::steady_clock::time_point::max();
	}

	Stopwatch Timer;
	ZEN_INFO("scrubbing STARTING (delete mode => {})", DoDelete);

	WorkerThreadPool ThreadPool{4, "scrubber"};
	ScrubContext	 Ctx{ThreadPool, Deadline};

	try
	{
		Ctx.SetShouldDelete(DoDelete);
		m_GcManager.ScrubStorage(Ctx);
	}
	catch (ScrubDeadlineExpiredException&)
	{
		ZEN_INFO("scrubbing deadline expired (top level), operation incomplete!");
	}

	ZEN_INFO("scrubbing DONE (in {})", NiceTimeSpanMs(Timer.GetElapsedTimeMs()));
}

void
GcScheduler::CollectGarbage(const GcClock::TimePoint& CacheExpireTime,
							const GcClock::TimePoint& ProjectStoreExpireTime,
							bool					  Delete,
							bool					  CollectSmallObjects,
							bool					  SkipCid)
{
	ZEN_TRACE_CPU("GcScheduler::CollectGarbage");

	GcContext GcCtx(CacheExpireTime, ProjectStoreExpireTime);
	GcCtx.SetDeletionMode(Delete);
	GcCtx.SetSkipCid(SkipCid);
	GcCtx.CollectSmallObjects(CollectSmallObjects);
	GcCtx.DiskReservePath(m_Config.RootDirectory / "reserve.gc");

	auto ReclaimDiskReserve = [&]() {
		std::error_code Ec = CreateGCReserve(m_Config.RootDirectory / "reserve.gc", m_Config.DiskReserveSize);
		if (Ec)
		{
			ZEN_WARN("unable to create GC reserve at '{}' with size {}, reason: '{}'",
					 m_Config.RootDirectory / "reserve.gc",
					 NiceBytes(m_Config.DiskReserveSize),
					 Ec.message());
		}
	};

	ReclaimDiskReserve();
	const auto _ = MakeGuard([&] { ReclaimDiskReserve(); });

	CheckDiskSpace();

	if (m_AreDiskWritesBlocked.load())
	{
		// We are low on disk, check if we can release our extra storage reserve, if we can't bail from doing GC
		uint64_t ReleasedSpace = GcCtx.ClaimGCReserve();
		if (ReleasedSpace == 0)
		{
			ZEN_WARN("Disk space is very low and we have no GC reserve, skipping GC as this requires at least some space to write to '{}'",
					 m_Config.RootDirectory);
			return;
		}
	}

	ZEN_INFO("garbage collection STARTING, small objects gc {}, {} CAS. Cache cutoff time {}, project store cutoff time {}",
			 GcCtx.CollectSmallObjects() ? "ENABLED"sv : "DISABLED"sv,
			 SkipCid ? "skip"sv : "include"sv,
			 CacheExpireTime,
			 ProjectStoreExpireTime);
	{
		Stopwatch  Timer;
		const auto __ = MakeGuard([&] { ZEN_INFO("garbage collection DONE in {}", NiceTimeSpanMs(Timer.GetElapsedTimeMs())); });

		m_GcManager.CollectGarbage(GcCtx);

		if (SkipCid)
		{
			m_LastLightweightGcTime = GcClock::Now();
		}
		else
		{
			if (Delete)
			{
				GcClock::TimePoint KeepRangeStart = Min(CacheExpireTime, ProjectStoreExpireTime);
				m_LastGcExpireTime				  = KeepRangeStart;
				std::unique_lock Lock(m_GcMutex);
				m_DiskUsageWindow.KeepRange(KeepRangeStart.time_since_epoch().count(), GcClock::Duration::max().count());
			}

			m_LastGcTime			= GcClock::Now();
			m_LastLightweightGcTime = m_LastGcTime;
		}

		try
		{
			const fs::path Path = m_Config.RootDirectory / "gc_state";
			ZEN_DEBUG("saving scheduler state to '{}'", Path);
			CbObjectWriter SchedulerState;
			SchedulerState << "LastGcTime"sv << static_cast<int64_t>(m_LastGcTime.time_since_epoch().count());
			SchedulerState << "LastGcExpireTime"sv << static_cast<int64_t>(m_LastGcExpireTime.time_since_epoch().count());
			SaveCompactBinaryObject(Path, SchedulerState.Save());
		}
		catch (std::system_error& SystemError)
		{
			if (IsOOM(SystemError.code()))
			{
				ZEN_WARN("writing gc scheduler state ran out of memory: '{}'", SystemError.what());
			}
			else if (IsOOD(SystemError.code()))
			{
				ZEN_WARN("writing gc scheduler state ran out of disk space: '{}'", SystemError.what());
			}
			else
			{
				ZEN_ERROR("writing gc scheduler state failed with system error exception: '{}'", SystemError.what());
			}
		}
		catch (std::bad_alloc& BadAlloc)
		{
			ZEN_WARN("writing gc scheduler state ran out of memory: '{}'", BadAlloc.what());
		}
		catch (std::exception& Ex)
		{
			ZEN_ERROR("writing gc scheduler state failed with: '{}'", Ex.what());
		}
	}
}

//////////////////////////////////////////////////////////////////////////

#if ZEN_WITH_TESTS

namespace gc::impl {
	static IoBuffer CreateChunk(uint64_t Size)
	{
		static std::random_device rd;
		static std::mt19937		  g(rd());

		std::vector<uint8_t> Values;
		Values.resize(Size);
		for (size_t Idx = 0; Idx < Size; ++Idx)
		{
			Values[Idx] = static_cast<uint8_t>(Idx);
		}
		std::shuffle(Values.begin(), Values.end(), g);

		return IoBufferBuilder::MakeCloneFromMemory(Values.data(), Values.size());
	}

	static CompressedBuffer Compress(IoBuffer Buffer)
	{
		return CompressedBuffer::Compress(SharedBuffer::MakeView(Buffer.GetData(), Buffer.GetSize()));
	}
}  // namespace gc::impl

TEST_CASE("gc.basic")
{
	using namespace gc::impl;

	ScopedTemporaryDirectory TempDir;

	CidStoreConfiguration CasConfig;
	CasConfig.RootDirectory = TempDir.Path() / "cas";

	GcManager Gc;
	CidStore  CidStore(Gc);

	CidStore.Initialize(CasConfig);

	IoBuffer Chunk			 = CreateChunk(128);
	auto	 CompressedChunk = Compress(Chunk);

	const auto InsertResult = CidStore.AddChunk(CompressedChunk.GetCompressed().Flatten().AsIoBuffer(), CompressedChunk.DecodeRawHash());
	CHECK(InsertResult.New);

	GcContext GcCtx(GcClock::Now() - std::chrono::hours(24), GcClock::Now() - std::chrono::hours(24));
	GcCtx.CollectSmallObjects(true);

	CidStore.Flush();
	Gc.CollectGarbage(GcCtx);

	CHECK(!CidStore.ContainsChunk(CompressedChunk.DecodeRawHash()));
}

TEST_CASE("gc.full")
{
	using namespace gc::impl;

	ScopedTemporaryDirectory TempDir;

	CidStoreConfiguration CasConfig;
	CasConfig.RootDirectory = TempDir.Path() / "cas";

	GcManager				  Gc;
	std::unique_ptr<CasStore> CasStore = CreateCasStore(Gc);

	CasStore->Initialize(CasConfig);

	uint64_t ChunkSizes[9]	= {128, 541, 1023, 781, 218, 37, 4, 997, 5};
	IoBuffer Chunks[9]		= {CreateChunk(ChunkSizes[0]),
						   CreateChunk(ChunkSizes[1]),
						   CreateChunk(ChunkSizes[2]),
						   CreateChunk(ChunkSizes[3]),
						   CreateChunk(ChunkSizes[4]),
						   CreateChunk(ChunkSizes[5]),
						   CreateChunk(ChunkSizes[6]),
						   CreateChunk(ChunkSizes[7]),
						   CreateChunk(ChunkSizes[8])};
	IoHash	 ChunkHashes[9] = {
		  IoHash::HashBuffer(Chunks[0].Data(), Chunks[0].Size()),
		  IoHash::HashBuffer(Chunks[1].Data(), Chunks[1].Size()),
		  IoHash::HashBuffer(Chunks[2].Data(), Chunks[2].Size()),
		  IoHash::HashBuffer(Chunks[3].Data(), Chunks[3].Size()),
		  IoHash::HashBuffer(Chunks[4].Data(), Chunks[4].Size()),
		  IoHash::HashBuffer(Chunks[5].Data(), Chunks[5].Size()),
		  IoHash::HashBuffer(Chunks[6].Data(), Chunks[6].Size()),
		  IoHash::HashBuffer(Chunks[7].Data(), Chunks[7].Size()),
		  IoHash::HashBuffer(Chunks[8].Data(), Chunks[8].Size()),
	  };

	CasStore->InsertChunk(Chunks[0], ChunkHashes[0]);
	CasStore->InsertChunk(Chunks[1], ChunkHashes[1]);
	CasStore->InsertChunk(Chunks[2], ChunkHashes[2]);
	CasStore->InsertChunk(Chunks[3], ChunkHashes[3]);
	CasStore->InsertChunk(Chunks[4], ChunkHashes[4]);
	CasStore->InsertChunk(Chunks[5], ChunkHashes[5]);
	CasStore->InsertChunk(Chunks[6], ChunkHashes[6]);
	CasStore->InsertChunk(Chunks[7], ChunkHashes[7]);
	CasStore->InsertChunk(Chunks[8], ChunkHashes[8]);

	CidStoreSize InitialSize = CasStore->TotalSize();

	// Keep first and last
	{
		GcContext GcCtx(GcClock::Now() - std::chrono::hours(24), GcClock::Now() - std::chrono::hours(24));
		GcCtx.CollectSmallObjects(true);

		std::vector<IoHash> KeepChunks;
		KeepChunks.push_back(ChunkHashes[0]);
		KeepChunks.push_back(ChunkHashes[8]);
		GcCtx.AddRetainedCids(KeepChunks);

		CasStore->Flush();
		Gc.CollectGarbage(GcCtx);

		CHECK(CasStore->ContainsChunk(ChunkHashes[0]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[1]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[2]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[3]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[4]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[5]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[6]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[7]));
		CHECK(CasStore->ContainsChunk(ChunkHashes[8]));

		CHECK(ChunkHashes[0] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[0])));
		CHECK(ChunkHashes[8] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[8])));
	}

	CasStore->InsertChunk(Chunks[1], ChunkHashes[1]);
	CasStore->InsertChunk(Chunks[2], ChunkHashes[2]);
	CasStore->InsertChunk(Chunks[3], ChunkHashes[3]);
	CasStore->InsertChunk(Chunks[4], ChunkHashes[4]);
	CasStore->InsertChunk(Chunks[5], ChunkHashes[5]);
	CasStore->InsertChunk(Chunks[6], ChunkHashes[6]);
	CasStore->InsertChunk(Chunks[7], ChunkHashes[7]);

	// Keep last
	{
		GcContext GcCtx(GcClock::Now() - std::chrono::hours(24), GcClock::Now() - std::chrono::hours(24));
		GcCtx.CollectSmallObjects(true);
		std::vector<IoHash> KeepChunks;
		KeepChunks.push_back(ChunkHashes[8]);
		GcCtx.AddRetainedCids(KeepChunks);

		CasStore->Flush();
		Gc.CollectGarbage(GcCtx);

		CHECK(!CasStore->ContainsChunk(ChunkHashes[0]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[1]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[2]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[3]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[4]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[5]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[6]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[7]));
		CHECK(CasStore->ContainsChunk(ChunkHashes[8]));

		CHECK(ChunkHashes[8] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[8])));

		CasStore->InsertChunk(Chunks[1], ChunkHashes[1]);
		CasStore->InsertChunk(Chunks[2], ChunkHashes[2]);
		CasStore->InsertChunk(Chunks[3], ChunkHashes[3]);
		CasStore->InsertChunk(Chunks[4], ChunkHashes[4]);
		CasStore->InsertChunk(Chunks[5], ChunkHashes[5]);
		CasStore->InsertChunk(Chunks[6], ChunkHashes[6]);
		CasStore->InsertChunk(Chunks[7], ChunkHashes[7]);
	}

	// Keep mixed
	{
		GcContext GcCtx(GcClock::Now() - std::chrono::hours(24), GcClock::Now() - std::chrono::hours(24));
		GcCtx.CollectSmallObjects(true);
		std::vector<IoHash> KeepChunks;
		KeepChunks.push_back(ChunkHashes[1]);
		KeepChunks.push_back(ChunkHashes[4]);
		KeepChunks.push_back(ChunkHashes[7]);
		GcCtx.AddRetainedCids(KeepChunks);

		CasStore->Flush();
		Gc.CollectGarbage(GcCtx);

		CHECK(!CasStore->ContainsChunk(ChunkHashes[0]));
		CHECK(CasStore->ContainsChunk(ChunkHashes[1]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[2]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[3]));
		CHECK(CasStore->ContainsChunk(ChunkHashes[4]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[5]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[6]));
		CHECK(CasStore->ContainsChunk(ChunkHashes[7]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[8]));

		CHECK(ChunkHashes[1] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[1])));
		CHECK(ChunkHashes[4] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[4])));
		CHECK(ChunkHashes[7] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[7])));

		CasStore->InsertChunk(Chunks[0], ChunkHashes[0]);
		CasStore->InsertChunk(Chunks[2], ChunkHashes[2]);
		CasStore->InsertChunk(Chunks[3], ChunkHashes[3]);
		CasStore->InsertChunk(Chunks[5], ChunkHashes[5]);
		CasStore->InsertChunk(Chunks[6], ChunkHashes[6]);
		CasStore->InsertChunk(Chunks[8], ChunkHashes[8]);
	}

	// Keep multiple at end
	{
		GcContext GcCtx(GcClock::Now() - std::chrono::hours(24), GcClock::Now() - std::chrono::hours(24));
		GcCtx.CollectSmallObjects(true);
		std::vector<IoHash> KeepChunks;
		KeepChunks.push_back(ChunkHashes[6]);
		KeepChunks.push_back(ChunkHashes[7]);
		KeepChunks.push_back(ChunkHashes[8]);
		GcCtx.AddRetainedCids(KeepChunks);

		CasStore->Flush();
		Gc.CollectGarbage(GcCtx);

		CHECK(!CasStore->ContainsChunk(ChunkHashes[0]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[1]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[2]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[3]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[4]));
		CHECK(!CasStore->ContainsChunk(ChunkHashes[5]));
		CHECK(CasStore->ContainsChunk(ChunkHashes[6]));
		CHECK(CasStore->ContainsChunk(ChunkHashes[7]));
		CHECK(CasStore->ContainsChunk(ChunkHashes[8]));

		CHECK(ChunkHashes[6] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[6])));
		CHECK(ChunkHashes[7] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[7])));
		CHECK(ChunkHashes[8] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[8])));

		CasStore->InsertChunk(Chunks[0], ChunkHashes[0]);
		CasStore->InsertChunk(Chunks[1], ChunkHashes[1]);
		CasStore->InsertChunk(Chunks[2], ChunkHashes[2]);
		CasStore->InsertChunk(Chunks[3], ChunkHashes[3]);
		CasStore->InsertChunk(Chunks[4], ChunkHashes[4]);
		CasStore->InsertChunk(Chunks[5], ChunkHashes[5]);
	}

	// Verify that we nicely appended blocks even after all GC operations
	CHECK(ChunkHashes[0] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[0])));
	CHECK(ChunkHashes[1] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[1])));
	CHECK(ChunkHashes[2] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[2])));
	CHECK(ChunkHashes[3] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[3])));
	CHECK(ChunkHashes[4] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[4])));
	CHECK(ChunkHashes[5] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[5])));
	CHECK(ChunkHashes[6] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[6])));
	CHECK(ChunkHashes[7] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[7])));
	CHECK(ChunkHashes[8] == IoHash::HashBuffer(CasStore->FindChunk(ChunkHashes[8])));

	auto FinalSize = CasStore->TotalSize();

	CHECK_LE(InitialSize.TinySize, FinalSize.TinySize);
	CHECK_GE(InitialSize.TinySize + (1u << 28), FinalSize.TinySize);
}

TEST_CASE("gc.diskusagewindow")
{
	using namespace gc::impl;

	DiskUsageWindow Stats;
	Stats.Append({.SampleTime = 0, .DiskUsage = 0});	// 0	0
	Stats.Append({.SampleTime = 10, .DiskUsage = 10});	// 1	10
	Stats.Append({.SampleTime = 20, .DiskUsage = 20});	// 2	10
	Stats.Append({.SampleTime = 30, .DiskUsage = 20});	// 3	0
	Stats.Append({.SampleTime = 40, .DiskUsage = 15});	// 4	0
	Stats.Append({.SampleTime = 50, .DiskUsage = 25});	// 5	10
	Stats.Append({.SampleTime = 60, .DiskUsage = 30});	// 6	5
	Stats.Append({.SampleTime = 70, .DiskUsage = 45});	// 7	15

	SUBCASE("Truncate start")
	{
		Stats.KeepRange(-15, 31);
		CHECK(Stats.m_LogWindow.size() == 4);
		CHECK(Stats.m_LogWindow[0].SampleTime == 0);
		CHECK(Stats.m_LogWindow[3].SampleTime == 30);
	}

	SUBCASE("Truncate end")
	{
		Stats.KeepRange(70, 71);
		CHECK(Stats.m_LogWindow.size() == 1);
		CHECK(Stats.m_LogWindow[0].SampleTime == 70);
	}

	SUBCASE("Truncate middle")
	{
		Stats.KeepRange(29, 69);
		CHECK(Stats.m_LogWindow.size() == 4);
		CHECK(Stats.m_LogWindow[0].SampleTime == 30);
		CHECK(Stats.m_LogWindow[3].SampleTime == 60);
	}

	SUBCASE("Full range")
	{
		uint64_t MaxDelta = 0;
		// 0-10, 10-20, 20-30, 30-40, 40-50, 50-60, 60-70, 70-80
		std::vector<uint64_t> DiskDeltas = Stats.GetDiskDeltas(0, 80, 10, MaxDelta);
		CHECK(DiskDeltas.size() == 8);
		CHECK(MaxDelta == 15);
		CHECK(DiskDeltas[0] == 0);
		CHECK(DiskDeltas[1] == 10);
		CHECK(DiskDeltas[2] == 10);
		CHECK(DiskDeltas[3] == 0);
		CHECK(DiskDeltas[4] == 0);
		CHECK(DiskDeltas[5] == 10);
		CHECK(DiskDeltas[6] == 5);
		CHECK(DiskDeltas[7] == 15);
	}

	SUBCASE("Sub range")
	{
		uint64_t			  MaxDelta	 = 0;
		std::vector<uint64_t> DiskDeltas = Stats.GetDiskDeltas(20, 40, 10, MaxDelta);
		CHECK(DiskDeltas.size() == 2);
		CHECK(MaxDelta == 10);
		CHECK(DiskDeltas[0] == 10);	 // [20:30]
		CHECK(DiskDeltas[1] == 0);	 // [30:40]
	}
	SUBCASE("Unaligned sub range 1")
	{
		uint64_t			  MaxDelta	 = 0;
		std::vector<uint64_t> DiskDeltas = Stats.GetDiskDeltas(21, 51, 10, MaxDelta);
		CHECK(DiskDeltas.size() == 3);
		CHECK(MaxDelta == 10);
		CHECK(DiskDeltas[0] == 0);	 // [21:31]
		CHECK(DiskDeltas[1] == 0);	 // [31:41]
		CHECK(DiskDeltas[2] == 10);	 // [41:51]
	}
	SUBCASE("Unaligned end range")
	{
		uint64_t			  MaxDelta	 = 0;
		std::vector<uint64_t> DiskDeltas = Stats.GetDiskDeltas(29, 79, 10, MaxDelta);
		CHECK(DiskDeltas.size() == 5);
		CHECK(MaxDelta == 15);
		CHECK(DiskDeltas[0] == 0);	 // [29:39]
		CHECK(DiskDeltas[1] == 0);	 // [39:49]
		CHECK(DiskDeltas[2] == 10);	 // [49:59]
		CHECK(DiskDeltas[3] == 5);	 // [59:69]
		CHECK(DiskDeltas[4] == 15);	 // [69:79]
	}
	SUBCASE("Ahead of window")
	{
		uint64_t			  MaxDelta	 = 0;
		std::vector<uint64_t> DiskDeltas = Stats.GetDiskDeltas(-40, 0, 10, MaxDelta);
		CHECK(DiskDeltas.size() == 4);
		CHECK(MaxDelta == 0);
		CHECK(DiskDeltas[0] == 0);	// [-40:-30]
		CHECK(DiskDeltas[1] == 0);	// [-30:-20]
		CHECK(DiskDeltas[2] == 0);	// [-20:-10]
		CHECK(DiskDeltas[3] == 0);	// [-10:0]
	}
	SUBCASE("After of window")
	{
		uint64_t			  MaxDelta	 = 0;
		std::vector<uint64_t> DiskDeltas = Stats.GetDiskDeltas(90, 120, 10, MaxDelta);
		CHECK(DiskDeltas.size() == 3);
		CHECK(MaxDelta == 0);
		CHECK(DiskDeltas[0] == 0);	// [90:100]
		CHECK(DiskDeltas[1] == 0);	// [100:110]
		CHECK(DiskDeltas[2] == 0);	// [110:120]
	}
	SUBCASE("Encapsulating window")
	{
		uint64_t			  MaxDelta	 = 0;
		std::vector<uint64_t> DiskDeltas = Stats.GetDiskDeltas(-20, 100, 10, MaxDelta);
		CHECK(DiskDeltas.size() == 12);
		CHECK(MaxDelta == 15);
		CHECK(DiskDeltas[0] == 0);	 // [-20:-10]
		CHECK(DiskDeltas[1] == 0);	 // [ -10:0]
		CHECK(DiskDeltas[2] == 0);	 // [0:10]
		CHECK(DiskDeltas[3] == 10);	 // [10:20]
		CHECK(DiskDeltas[4] == 10);	 // [20:30]
		CHECK(DiskDeltas[5] == 0);	 // [30:40]
		CHECK(DiskDeltas[6] == 0);	 // [40:50]
		CHECK(DiskDeltas[7] == 10);	 // [50:60]
		CHECK(DiskDeltas[8] == 5);	 // [60:70]
		CHECK(DiskDeltas[9] == 15);	 // [70:80]
		CHECK(DiskDeltas[10] == 0);	 // [80:90]
		CHECK(DiskDeltas[11] == 0);	 // [90:100]
	}

	SUBCASE("Full range half stride")
	{
		uint64_t			  MaxDelta	 = 0;
		std::vector<uint64_t> DiskDeltas = Stats.GetDiskDeltas(0, 80, 20, MaxDelta);
		CHECK(DiskDeltas.size() == 4);
		CHECK(MaxDelta == 20);
		CHECK(DiskDeltas[0] == 10);	 // [0:20]
		CHECK(DiskDeltas[1] == 10);	 // [20:40]
		CHECK(DiskDeltas[2] == 10);	 // [40:60]
		CHECK(DiskDeltas[3] == 20);	 // [60:80]
	}

	SUBCASE("Partial odd stride")
	{
		uint64_t			  MaxDelta	 = 0;
		std::vector<uint64_t> DiskDeltas = Stats.GetDiskDeltas(13, 67, 18, MaxDelta);
		CHECK(DiskDeltas.size() == 3);
		CHECK(MaxDelta == 15);
		CHECK(DiskDeltas[0] == 10);	 // [13:31]
		CHECK(DiskDeltas[1] == 0);	 // [31:49]
		CHECK(DiskDeltas[2] == 15);	 // [49:67]
	}

	SUBCASE("Find size window")
	{
		DiskUsageWindow Empty;
		CHECK(Empty.FindTimepointThatRemoves(15u, 10000) == 10000);

		CHECK(Stats.FindTimepointThatRemoves(15u, 40) == 21);
		CHECK(Stats.FindTimepointThatRemoves(15u, 20) == 20);
		CHECK(Stats.FindTimepointThatRemoves(100000u, 50) == 50);
		CHECK(Stats.FindTimepointThatRemoves(100000u, 1000));
	}
}

TEST_CASE("scrub.basic")
{
	using namespace gc::impl;

	ScopedTemporaryDirectory TempDir;

	CidStoreConfiguration CasConfig;
	CasConfig.RootDirectory = TempDir.Path() / "cas";

	GcManager Gc;
	CidStore  CidStore(Gc);

	CidStore.Initialize(CasConfig);

	IoBuffer Chunk			 = CreateChunk(128);
	auto	 CompressedChunk = Compress(Chunk);

	const auto InsertResult = CidStore.AddChunk(CompressedChunk.GetCompressed().Flatten().AsIoBuffer(), CompressedChunk.DecodeRawHash());
	CHECK(InsertResult.New);

	GcContext GcCtx(GcClock::Now() - std::chrono::hours(24), GcClock::Now() - std::chrono::hours(24));
	GcCtx.CollectSmallObjects(true);

	CidStore.Flush();
	Gc.CollectGarbage(GcCtx);

	CHECK(!CidStore.ContainsChunk(CompressedChunk.DecodeRawHash()));
}

#endif

void
gc_forcelink()
{
}

}  // namespace zen