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

#include "structuredcachestore.h"

#include <zencore/except.h>

#include <zencore/compactbinarybuilder.h>
#include <zencore/compactbinarypackage.h>
#include <zencore/compactbinaryvalidation.h>
#include <zencore/compress.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/thread.h>
#include <zencore/timer.h>
#include <zencore/trace.h>
#include <zenstore/cidstore.h>

#include <xxhash.h>

#if ZEN_PLATFORM_WINDOWS
#	include <zencore/windows.h>
#endif

ZEN_THIRD_PARTY_INCLUDES_START
#include <fmt/core.h>
#include <gsl/gsl-lite.hpp>
ZEN_THIRD_PARTY_INCLUDES_END

#if ZEN_WITH_TESTS
#	include <zencore/testing.h>
#	include <zencore/testutils.h>
#	include <zencore/workthreadpool.h>
#	include <random>
#endif

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

#pragma pack(push)
#pragma pack(1)

namespace zen {

namespace {

#pragma pack(push)
#pragma pack(1)

	struct CacheBucketIndexHeader
	{
		static constexpr uint32_t ExpectedMagic	 = 0x75696478;	// 'uidx';
		static constexpr uint32_t CurrentVersion = 1;

		uint32_t Magic			  = ExpectedMagic;
		uint32_t Version		  = CurrentVersion;
		uint64_t EntryCount		  = 0;
		uint64_t LogPosition	  = 0;
		uint32_t PayloadAlignment = 0;
		uint32_t Checksum		  = 0;

		static uint32_t ComputeChecksum(const CacheBucketIndexHeader& Header)
		{
			return XXH32(&Header.Magic, sizeof(CacheBucketIndexHeader) - sizeof(uint32_t), 0xC0C0'BABA);
		}
	};

	static_assert(sizeof(CacheBucketIndexHeader) == 32);

	struct LegacyDiskLocation
	{
		inline LegacyDiskLocation() = default;

		inline LegacyDiskLocation(uint64_t Offset, uint64_t ValueSize, uint32_t IndexSize, uint64_t Flags)
		: OffsetAndFlags(CombineOffsetAndFlags(Offset, Flags))
		, LowerSize(ValueSize & 0xFFFFffff)
		, IndexDataSize(IndexSize)
		{
		}

		static const uint64_t kOffsetMask = 0x0000'ffFF'ffFF'ffFFull;
		static const uint64_t kSizeMask	  = 0x00FF'0000'0000'0000ull;  // Most significant bits of value size (lower 32 bits in LowerSize)
		static const uint64_t kFlagsMask  = 0xff00'0000'0000'0000ull;
		static const uint64_t kStandaloneFile = 0x8000'0000'0000'0000ull;  // Stored as a separate file
		static const uint64_t kStructured	  = 0x4000'0000'0000'0000ull;  // Serialized as compact binary
		static const uint64_t kTombStone	  = 0x2000'0000'0000'0000ull;  // Represents a deleted key/value
		static const uint64_t kCompressed	  = 0x1000'0000'0000'0000ull;  // Stored in compressed buffer format

		static uint64_t CombineOffsetAndFlags(uint64_t Offset, uint64_t Flags) { return Offset | Flags; }

		inline uint64_t		  Offset() const { return OffsetAndFlags & kOffsetMask; }
		inline uint64_t		  Size() const { return LowerSize; }
		inline uint64_t		  IsFlagSet(uint64_t Flag) const { return OffsetAndFlags & Flag; }
		inline ZenContentType GetContentType() const
		{
			ZenContentType ContentType = ZenContentType::kBinary;

			if (IsFlagSet(LegacyDiskLocation::kStructured))
			{
				ContentType = ZenContentType::kCbObject;
			}

			if (IsFlagSet(LegacyDiskLocation::kCompressed))
			{
				ContentType = ZenContentType::kCompressedBinary;
			}

			return ContentType;
		}
		inline uint64_t Flags() const { return OffsetAndFlags & kFlagsMask; }

	private:
		uint64_t OffsetAndFlags = 0;
		uint32_t LowerSize		= 0;
		uint32_t IndexDataSize	= 0;
	};

	struct LegacyDiskIndexEntry
	{
		IoHash			   Key;
		LegacyDiskLocation Location;
	};

#pragma pack(pop)

	static_assert(sizeof(LegacyDiskIndexEntry) == 36);

	const char* IndexExtension = ".uidx";
	const char* LogExtension   = ".slog";
	const char* DataExtension  = ".sobs";

	std::filesystem::path GetBlockPath(const std::filesystem::path& BlocksBasePath, const uint32_t BlockIndex)
	{
		ExtendablePathBuilder<256> Path;

		char BlockHexString[9];
		ToHexNumber(BlockIndex, BlockHexString);

		Path.Append(BlocksBasePath);
		Path.AppendSeparator();
		Path.AppendAsciiRange(BlockHexString, BlockHexString + 4);
		Path.AppendSeparator();
		Path.Append(BlockHexString);
		Path.Append(DataExtension);
		return Path.ToPath();
	}

	std::filesystem::path GetIndexPath(const std::filesystem::path& BucketDir, const std::string& BucketName)
	{
		return BucketDir / (BucketName + IndexExtension);
	}

	std::filesystem::path GetTempIndexPath(const std::filesystem::path& BucketDir, const std::string& BucketName)
	{
		return BucketDir / (BucketName + ".tmp" + IndexExtension);
	}

	std::filesystem::path GetLogPath(const std::filesystem::path& BucketDir, const std::string& BucketName)
	{
		return BucketDir / (BucketName + LogExtension);
	}

	std::filesystem::path GetLegacyLogPath(const std::filesystem::path& BucketDir)
	{
		return BucketDir / (std::string("zen") + LogExtension);
	}

	std::filesystem::path GetLegacyDataPath(const std::filesystem::path& BucketDir)
	{
		return BucketDir / (std::string("zen") + DataExtension);
	}

	std::vector<DiskIndexEntry> MakeDiskIndexEntries(const std::unordered_map<IoHash, DiskLocation>& MovedChunks,
													 const std::vector<IoHash>&						 DeletedChunks)
	{
		std::vector<DiskIndexEntry> result;
		result.reserve(MovedChunks.size());
		for (const auto& MovedEntry : MovedChunks)
		{
			result.push_back({.Key = MovedEntry.first, .Location = MovedEntry.second});
		}
		for (const IoHash& ChunkHash : DeletedChunks)
		{
			DiskLocation Location;
			Location.Flags |= DiskLocation::kTombStone;
			result.push_back({.Key = ChunkHash, .Location = Location});
		}
		return result;
	}

	bool ValidateLegacyEntry(const LegacyDiskIndexEntry& Entry, std::string& OutReason)
	{
		if (Entry.Key == IoHash::Zero)
		{
			OutReason = fmt::format("Invalid hash key {}", Entry.Key.ToHexString());
			return false;
		}
		if (Entry.Location.Flags() & ~(LegacyDiskLocation::kStandaloneFile | LegacyDiskLocation::kStructured |
									   LegacyDiskLocation::kTombStone | LegacyDiskLocation::kCompressed))
		{
			OutReason = fmt::format("Invalid flags {} for entry {}", Entry.Location.Flags(), Entry.Key.ToHexString());
			return false;
		}
		if (!Entry.Location.IsFlagSet(LegacyDiskLocation::kTombStone))
		{
			return true;
		}
		uint64_t Size = Entry.Location.Size();
		if (Size == 0)
		{
			OutReason = fmt::format("Invalid size {} for entry {}", Size, Entry.Key.ToHexString());
			return false;
		}
		return true;
	}

	bool ValidateEntry(const DiskIndexEntry& Entry, std::string& OutReason)
	{
		if (Entry.Key == IoHash::Zero)
		{
			OutReason = fmt::format("Invalid hash key {}", Entry.Key.ToHexString());
			return false;
		}
		if (Entry.Location.GetFlags() &
			~(DiskLocation::kStandaloneFile | DiskLocation::kStructured | DiskLocation::kTombStone | DiskLocation::kCompressed))
		{
			OutReason = fmt::format("Invalid flags {} for entry {}", Entry.Location.GetFlags(), Entry.Key.ToHexString());
			return false;
		}
		if (Entry.Location.IsFlagSet(DiskLocation::kTombStone))
		{
			return true;
		}
		uint64_t Size = Entry.Location.Size();
		if (Size == 0)
		{
			OutReason = fmt::format("Invalid size {} for entry {}", Size, Entry.Key.ToHexString());
			return false;
		}
		return true;
	}

}  // namespace

namespace fs = std::filesystem;

static 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();
}

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

ZenCacheStore::ZenCacheStore(CasGc& Gc, const std::filesystem::path& RootDir)
: GcStorage(Gc)
, GcContributor(Gc)
, m_RootDir(RootDir)
, m_DiskLayer(RootDir)
{
	ZEN_INFO("initializing structured cache at '{}'", RootDir);
	CreateDirectories(RootDir);

	m_DiskLayer.DiscoverBuckets();

#if ZEN_USE_CACHE_TRACKER
	m_AccessTracker.reset(new ZenCacheTracker(RootDir));
#endif
}

ZenCacheStore::~ZenCacheStore()
{
}

bool
ZenCacheStore::Get(std::string_view InBucket, const IoHash& HashKey, ZenCacheValue& OutValue)
{
	ZEN_TRACE_CPU("Z$::Get");

	bool Ok = m_MemLayer.Get(InBucket, HashKey, OutValue);

#if ZEN_USE_CACHE_TRACKER
	auto _ = MakeGuard([&] {
		if (!Ok)
			return;

		m_AccessTracker->TrackAccess(InBucket, HashKey);
	});
#endif

	if (Ok)
	{
		ZEN_ASSERT(OutValue.Value.Size());

		return true;
	}

	Ok = m_DiskLayer.Get(InBucket, HashKey, OutValue);

	if (Ok)
	{
		ZEN_ASSERT(OutValue.Value.Size());

		if (OutValue.Value.Size() <= m_DiskLayerSizeThreshold)
		{
			m_MemLayer.Put(InBucket, HashKey, OutValue);
		}
	}

	return Ok;
}

void
ZenCacheStore::Put(std::string_view InBucket, const IoHash& HashKey, const ZenCacheValue& Value)
{
	ZEN_TRACE_CPU("Z$::Put");

	// Store value and index

	ZEN_ASSERT(Value.Value.Size());

	m_DiskLayer.Put(InBucket, HashKey, Value);

#if ZEN_USE_REF_TRACKING
	if (Value.Value.GetContentType() == ZenContentType::kCbObject)
	{
		if (ValidateCompactBinary(Value.Value, CbValidateMode::All) == CbValidateError::None)
		{
			CbObject Object{SharedBuffer(Value.Value)};

			uint8_t								TempBuffer[8 * sizeof(IoHash)];
			std::pmr::monotonic_buffer_resource Linear{TempBuffer, sizeof TempBuffer};
			std::pmr::polymorphic_allocator		Allocator{&Linear};
			std::pmr::vector<IoHash>			CidReferences{Allocator};

			Object.IterateAttachments([&](CbFieldView Field) { CidReferences.push_back(Field.AsAttachment()); });

			m_Gc.OnNewCidReferences(CidReferences);
		}
	}
#endif

	if (Value.Value.Size() <= m_DiskLayerSizeThreshold)
	{
		m_MemLayer.Put(InBucket, HashKey, Value);
	}
}

bool
ZenCacheStore::DropBucket(std::string_view Bucket)
{
	ZEN_INFO("dropping bucket '{}'", Bucket);

	// TODO: should ensure this is done atomically across all layers

	const bool MemDropped  = m_MemLayer.DropBucket(Bucket);
	const bool DiskDropped = m_DiskLayer.DropBucket(Bucket);
	const bool AnyDropped  = MemDropped || DiskDropped;

	ZEN_INFO("bucket '{}' was {}", Bucket, AnyDropped ? "dropped" : "not found");

	return AnyDropped;
}

void
ZenCacheStore::Flush()
{
	m_DiskLayer.Flush();
}

void
ZenCacheStore::Scrub(ScrubContext& Ctx)
{
	if (m_LastScrubTime == Ctx.ScrubTimestamp())
	{
		return;
	}

	m_LastScrubTime = Ctx.ScrubTimestamp();

	m_DiskLayer.Scrub(Ctx);
	m_MemLayer.Scrub(Ctx);
}

void
ZenCacheStore::GatherReferences(GcContext& GcCtx)
{
	Stopwatch  Timer;
	const auto Guard = MakeGuard(
		[this, &Timer] { ZEN_INFO("cache gathered all references from '{}' in {}", m_RootDir, NiceTimeSpanMs(Timer.GetElapsedTimeMs())); });

	access_tracking::AccessTimes AccessTimes;
	m_MemLayer.GatherAccessTimes(AccessTimes);

	m_DiskLayer.UpdateAccessTimes(AccessTimes);
	m_DiskLayer.GatherReferences(GcCtx);
}

void
ZenCacheStore::CollectGarbage(GcContext& GcCtx)
{
	m_MemLayer.Reset();
	m_DiskLayer.CollectGarbage(GcCtx);
}

GcStorageSize
ZenCacheStore::StorageSize() const
{
	return {.DiskSize = m_DiskLayer.TotalSize(), .MemorySize = m_MemLayer.TotalSize()};
}

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

ZenCacheMemoryLayer::ZenCacheMemoryLayer()
{
}

ZenCacheMemoryLayer::~ZenCacheMemoryLayer()
{
}

bool
ZenCacheMemoryLayer::Get(std::string_view InBucket, const IoHash& HashKey, ZenCacheValue& OutValue)
{
	RwLock::SharedLockScope _(m_Lock);

	auto it = m_Buckets.find(std::string(InBucket));

	if (it == m_Buckets.end())
	{
		return false;
	}

	CacheBucket* Bucket = &it->second;

	_.ReleaseNow();

	// There's a race here. Since the lock is released early to allow
	// inserts, the bucket delete path could end up deleting the
	// underlying data structure

	return Bucket->Get(HashKey, OutValue);
}

void
ZenCacheMemoryLayer::Put(std::string_view InBucket, const IoHash& HashKey, const ZenCacheValue& Value)
{
	CacheBucket* Bucket = nullptr;

	{
		RwLock::SharedLockScope _(m_Lock);

		if (auto It = m_Buckets.find(std::string(InBucket)); It != m_Buckets.end())
		{
			Bucket = &It->second;
		}
	}

	if (Bucket == nullptr)
	{
		// New bucket

		RwLock::ExclusiveLockScope _(m_Lock);

		if (auto It = m_Buckets.find(std::string(InBucket)); It != m_Buckets.end())
		{
			Bucket = &It->second;
		}
		else
		{
			Bucket = &m_Buckets[std::string(InBucket)];
		}
	}

	// Note that since the underlying IoBuffer is retained, the content type is also

	Bucket->Put(HashKey, Value);
}

bool
ZenCacheMemoryLayer::DropBucket(std::string_view Bucket)
{
	RwLock::ExclusiveLockScope _(m_Lock);

	return !!m_Buckets.erase(std::string(Bucket));
}

void
ZenCacheMemoryLayer::Scrub(ScrubContext& Ctx)
{
	RwLock::SharedLockScope _(m_Lock);

	for (auto& Kv : m_Buckets)
	{
		Kv.second.Scrub(Ctx);
	}
}

void
ZenCacheMemoryLayer::GatherAccessTimes(zen::access_tracking::AccessTimes& AccessTimes)
{
	using namespace zen::access_tracking;

	RwLock::SharedLockScope _(m_Lock);

	for (auto& Kv : m_Buckets)
	{
		std::vector<KeyAccessTime>& Bucket = AccessTimes.Buckets[Kv.first];
		Kv.second.GatherAccessTimes(Bucket);
	}
}

void
ZenCacheMemoryLayer::Reset()
{
	RwLock::ExclusiveLockScope _(m_Lock);
	m_Buckets.clear();
}

uint64_t
ZenCacheMemoryLayer::TotalSize() const
{
	uint64_t				TotalSize{};
	RwLock::SharedLockScope _(m_Lock);

	for (auto& Kv : m_Buckets)
	{
		TotalSize += Kv.second.TotalSize();
	}

	return TotalSize;
}

void
ZenCacheMemoryLayer::CacheBucket::Scrub(ScrubContext& Ctx)
{
	RwLock::SharedLockScope _(m_BucketLock);

	std::vector<IoHash> BadHashes;

	for (auto& Kv : m_CacheMap)
	{
		if (Kv.first != IoHash::HashBuffer(Kv.second.Payload))
		{
			BadHashes.push_back(Kv.first);
		}
	}

	if (!BadHashes.empty())
	{
		Ctx.ReportBadCasChunks(BadHashes);
	}
}

void
ZenCacheMemoryLayer::CacheBucket::GatherAccessTimes(std::vector<zen::access_tracking::KeyAccessTime>& AccessTimes)
{
	RwLock::SharedLockScope _(m_BucketLock);
	std::transform(m_CacheMap.begin(), m_CacheMap.end(), std::back_inserter(AccessTimes), [](const auto& Kv) {
		return access_tracking::KeyAccessTime{.Key = Kv.first, .LastAccess = Kv.second.LastAccess};
	});
}

bool
ZenCacheMemoryLayer::CacheBucket::Get(const IoHash& HashKey, ZenCacheValue& OutValue)
{
	RwLock::SharedLockScope _(m_BucketLock);

	if (auto It = m_CacheMap.find(HashKey); It != m_CacheMap.end())
	{
		BucketValue& Value = It.value();
		OutValue.Value	   = Value.Payload;

		Value.LastAccess.store(GcClock::TickCount(), std::memory_order_relaxed);

		return true;
	}

	return false;
}

void
ZenCacheMemoryLayer::CacheBucket::Put(const IoHash& HashKey, const ZenCacheValue& Value)
{
	{
		RwLock::ExclusiveLockScope _(m_BucketLock);
		m_CacheMap.insert_or_assign(HashKey, BucketValue(Value.Value, GcClock::TickCount()));
	}

	m_TotalSize.fetch_add(Value.Value.GetSize(), std::memory_order_seq_cst);
}

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

ZenCacheDiskLayer::CacheBucket::CacheBucket(std::string BucketName) : m_BucketName(std::move(BucketName))
{
}

ZenCacheDiskLayer::CacheBucket::~CacheBucket()
{
}

bool
ZenCacheDiskLayer::CacheBucket::Delete(std::filesystem::path BucketDir)
{
	if (std::filesystem::exists(BucketDir))
	{
		DeleteDirectories(BucketDir);

		return true;
	}

	return false;
}

void
ZenCacheDiskLayer::CacheBucket::OpenOrCreate(std::filesystem::path BucketDir, bool AllowCreate)
{
	using namespace std::literals;

	m_BlocksBasePath = BucketDir / "blocks";

	CreateDirectories(BucketDir);

	std::filesystem::path ManifestPath{BucketDir / "zen_manifest"};

	bool IsNew = false;

	CbObject Manifest = LoadCompactBinaryObject(ManifestPath);

	if (Manifest)
	{
		m_BucketId = Manifest["BucketId"].AsObjectId();
		m_IsOk	   = m_BucketId != Oid::Zero;
	}
	else if (AllowCreate)
	{
		m_BucketId.Generate();

		CbObjectWriter Writer;
		Writer << "BucketId"sv << m_BucketId;
		Manifest = Writer.Save();
		SaveCompactBinaryObject(ManifestPath, Manifest);
		IsNew = true;
	}
	else
	{
		return;
	}

	OpenLog(BucketDir, IsNew);

	for (CbFieldView Entry : Manifest["Timestamps"])
	{
		const CbObjectView Obj = Entry.AsObjectView();
		const IoHash	   Key = Obj["Key"sv].AsHash();

		if (auto It = m_Index.find(Key); It != m_Index.end())
		{
			It.value().LastAccess.store(Obj["LastAccess"sv].AsInt64(), std::memory_order_relaxed);
		}
	}

	m_IsOk = true;
}

void
ZenCacheDiskLayer::CacheBucket::MakeIndexSnapshot()
{
	ZEN_INFO("write store snapshot for '{}'", m_BucketDir / m_BucketName);
	uint64_t   EntryCount = 0;
	Stopwatch  Timer;
	const auto _ = MakeGuard([this, &EntryCount, &Timer] {
		ZEN_INFO("wrote store snapshot for '{}' containing #{} entries in {}",
				 m_BucketDir / m_BucketName,
				 EntryCount,
				 NiceTimeSpanMs(Timer.GetElapsedTimeMs()));
	});

	namespace fs = std::filesystem;

	fs::path IndexPath	   = GetIndexPath(m_BucketDir, m_BucketName);
	fs::path STmpIndexPath = GetTempIndexPath(m_BucketDir, m_BucketName);

	// Move index away, we keep it if something goes wrong
	if (fs::is_regular_file(STmpIndexPath))
	{
		fs::remove(STmpIndexPath);
	}
	if (fs::is_regular_file(IndexPath))
	{
		fs::rename(IndexPath, STmpIndexPath);
	}

	try
	{
		m_SlogFile.Flush();

		// Write the current state of the location map to a new index state
		uint64_t					LogCount = 0;
		std::vector<DiskIndexEntry> Entries;

		{
			RwLock::SharedLockScope __(m_InsertLock);
			RwLock::SharedLockScope ___(m_IndexLock);
			Entries.resize(m_Index.size());

			uint64_t EntryIndex = 0;
			for (auto& Entry : m_Index)
			{
				DiskIndexEntry& IndexEntry = Entries[EntryIndex++];
				IndexEntry.Key			   = Entry.first;
				IndexEntry.Location		   = Entry.second.Location;
			}

			LogCount = m_SlogFile.GetLogCount();
		}

		BasicFile ObjectIndexFile;
		ObjectIndexFile.Open(IndexPath, BasicFile::Mode::kTruncate);
		CacheBucketIndexHeader Header = {.EntryCount	   = Entries.size(),
										 .LogPosition	   = LogCount,
										 .PayloadAlignment = gsl::narrow<uint32_t>(m_PayloadAlignment)};

		Header.Checksum = CacheBucketIndexHeader::ComputeChecksum(Header);

		ObjectIndexFile.Write(&Header, sizeof(CacheBucketIndexHeader), 0);
		ObjectIndexFile.Write(Entries.data(), Entries.size() * sizeof(DiskIndexEntry), sizeof(CacheBucketIndexHeader));
		ObjectIndexFile.Flush();
		ObjectIndexFile.Close();
		EntryCount = Entries.size();
	}
	catch (std::exception& Err)
	{
		ZEN_ERROR("snapshot FAILED, reason: '{}'", Err.what());

		// Restore any previous snapshot

		if (fs::is_regular_file(STmpIndexPath))
		{
			fs::remove(IndexPath);
			fs::rename(STmpIndexPath, IndexPath);
		}
	}
	if (fs::is_regular_file(STmpIndexPath))
	{
		fs::remove(STmpIndexPath);
	}
}

uint64_t
ZenCacheDiskLayer::CacheBucket::ReadIndexFile()
{
	std::vector<DiskIndexEntry> Entries;
	std::filesystem::path		IndexPath = GetIndexPath(m_BucketDir, m_BucketName);
	if (std::filesystem::is_regular_file(IndexPath))
	{
		Stopwatch  Timer;
		const auto _ = MakeGuard([this, &Entries, &Timer] {
			ZEN_INFO("read store '{}' index containing #{} entries in {}",
					 m_BucketDir / m_BucketName,
					 Entries.size(),
					 NiceTimeSpanMs(Timer.GetElapsedTimeMs()));
		});

		BasicFile ObjectIndexFile;
		ObjectIndexFile.Open(IndexPath, BasicFile::Mode::kRead);
		uint64_t Size = ObjectIndexFile.FileSize();
		if (Size >= sizeof(CacheBucketIndexHeader))
		{
			uint64_t			   ExpectedEntryCount = (Size - sizeof(sizeof(CacheBucketIndexHeader))) / sizeof(DiskIndexEntry);
			CacheBucketIndexHeader Header;
			ObjectIndexFile.Read(&Header, sizeof(Header), 0);
			if ((Header.Magic == CacheBucketIndexHeader::ExpectedMagic) && (Header.Version == CacheBucketIndexHeader::CurrentVersion) &&
				(Header.Checksum == CacheBucketIndexHeader::ComputeChecksum(Header)) && (Header.PayloadAlignment > 0) &&
				(Header.EntryCount <= ExpectedEntryCount))
			{
				Entries.resize(Header.EntryCount);
				ObjectIndexFile.Read(Entries.data(), Header.EntryCount * sizeof(DiskIndexEntry), sizeof(CacheBucketIndexHeader));
				m_PayloadAlignment = Header.PayloadAlignment;

				std::string InvalidEntryReason;
				for (const DiskIndexEntry& Entry : Entries)
				{
					if (!ValidateEntry(Entry, InvalidEntryReason))
					{
						ZEN_WARN("skipping invalid entry in '{}', reason: '{}'", IndexPath, InvalidEntryReason);
						continue;
					}
					m_Index.insert_or_assign(Entry.Key, IndexEntry(Entry.Location, GcClock::TickCount()));
				}

				return Header.LogPosition;
			}
			else
			{
				ZEN_WARN("skipping invalid index file '{}'", IndexPath);
			}
		}
	}
	return 0;
}

uint64_t
ZenCacheDiskLayer::CacheBucket::ReadLog(uint64_t SkipEntryCount)
{
	std::vector<DiskIndexEntry> Entries;
	std::filesystem::path		LogPath = GetLogPath(m_BucketDir, m_BucketName);
	if (std::filesystem::is_regular_file(LogPath))
	{
		Stopwatch					Timer;
		const auto					_ = MakeGuard([LogPath, &Entries, &Timer] {
			 ZEN_INFO("read store '{}' log containing #{} entries in {}", LogPath, Entries.size(), NiceTimeSpanMs(Timer.GetElapsedTimeMs()));
		 });
		TCasLogFile<DiskIndexEntry> CasLog;
		CasLog.Open(LogPath, CasLogFile::Mode::kRead);
		if (CasLog.Initialize())
		{
			uint64_t EntryCount = CasLog.GetLogCount();
			if (EntryCount < SkipEntryCount)
			{
				ZEN_WARN("reading full log at '{}', reason: Log position from index snapshot is out of range", LogPath);
				SkipEntryCount = 0;
			}
			uint64_t ReadCount = EntryCount - SkipEntryCount;
			m_Index.reserve(ReadCount);
			uint64_t InvalidEntryCount = 0;
			CasLog.Replay(
				[&](const DiskIndexEntry& Record) {
					std::string InvalidEntryReason;
					if (Record.Location.Flags & DiskLocation::kTombStone)
					{
						m_Index.erase(Record.Key);
						return;
					}
					if (!ValidateEntry(Record, InvalidEntryReason))
					{
						ZEN_WARN("skipping invalid entry in '{}', reason: '{}'", LogPath, InvalidEntryReason);
						++InvalidEntryCount;
						return;
					}
					m_Index.insert_or_assign(Record.Key, IndexEntry(Record.Location, GcClock::TickCount()));
				},
				SkipEntryCount);
			if (InvalidEntryCount)
			{
				ZEN_WARN("found #{} invalid entries in '{}'", InvalidEntryCount, m_BucketDir / m_BucketName);
			}
		}
	}
	return 0;
};

uint64_t
ZenCacheDiskLayer::CacheBucket::MigrateLegacyData(bool CleanSource)
{
	std::filesystem::path LegacyLogPath = GetLegacyLogPath(m_BucketDir);

	if (!std::filesystem::is_regular_file(LegacyLogPath) || std::filesystem::file_size(LegacyLogPath) == 0)
	{
		return 0;
	}

	ZEN_INFO("migrating store {}", m_BucketDir / m_BucketName);

	std::filesystem::path LegacyDataPath = GetLegacyDataPath(m_BucketDir);

	uint64_t   MigratedChunkCount = 0;
	uint32_t   MigratedBlockCount = 0;
	Stopwatch  MigrationTimer;
	uint64_t   TotalSize = 0;
	const auto _		 = MakeGuard([this, &MigrationTimer, &MigratedChunkCount, &MigratedBlockCount, &TotalSize] {
		ZEN_INFO("migrated store '{}' to #{} chunks in #{} blocks in {} ({})",
				 m_BucketDir / m_BucketName,
				 MigratedChunkCount,
				 MigratedBlockCount,
				 NiceTimeSpanMs(MigrationTimer.GetElapsedTimeMs()),
				 NiceBytes(TotalSize));
	});

	uint32_t WriteBlockIndex = 0;
	while (std::filesystem::exists(GetBlockPath(m_BlocksBasePath, WriteBlockIndex)))
	{
		++WriteBlockIndex;
	}

	std::error_code Error;
	DiskSpace		Space = DiskSpaceInfo(m_BucketDir, Error);
	if (Error)
	{
		ZEN_ERROR("get disk space in '{}' FAILED, reason: '{}'", m_BucketDir, Error.message());
		return 0;
	}

	if (Space.Free < MaxBlockSize)
	{
		ZEN_ERROR("legacy store migration from '{}' FAILED, required disk space {}, free {}",
				  m_BucketDir / m_BucketName,
				  MaxBlockSize,
				  NiceBytes(Space.Free));
		return 0;
	}

	BasicFile BlockFile;
	BlockFile.Open(LegacyDataPath, CleanSource ? BasicFile::Mode::kWrite : BasicFile::Mode::kRead);

	std::unordered_map<IoHash, LegacyDiskIndexEntry, IoHash::Hasher> LegacyDiskIndex;
	uint64_t														 InvalidEntryCount = 0;

	TCasLogFile<LegacyDiskIndexEntry> LegacyCasLog;
	LegacyCasLog.Open(LegacyLogPath, CleanSource ? CasLogFile::Mode::kWrite : CasLogFile::Mode::kRead);
	{
		Stopwatch  Timer;
		const auto __ = MakeGuard([LegacyLogPath, &LegacyDiskIndex, &Timer] {
			ZEN_INFO("read store '{}' legacy log containing #{} entries in {}",
					 LegacyLogPath,
					 LegacyDiskIndex.size(),
					 NiceTimeSpanMs(Timer.GetElapsedTimeMs()));
		});
		if (LegacyCasLog.Initialize())
		{
			LegacyDiskIndex.reserve(LegacyCasLog.GetLogCount());
			LegacyCasLog.Replay(
				[&](const LegacyDiskIndexEntry& Record) {
					if (Record.Location.IsFlagSet(LegacyDiskLocation::kTombStone))
					{
						LegacyDiskIndex.erase(Record.Key);
						return;
					}
					std::string InvalidEntryReason;
					if (!ValidateLegacyEntry(Record, InvalidEntryReason))
					{
						ZEN_WARN("skipping invalid entry in '{}', reason: '{}'", LegacyLogPath, InvalidEntryReason);
						++InvalidEntryCount;
						return;
					}
					if (m_Index.contains(Record.Key))
					{
						return;
					}
					LegacyDiskIndex[Record.Key] = Record;
				},
				0);

			std::vector<IoHash> BadEntries;
			uint64_t			BlockFileSize = BlockFile.FileSize();
			for (const auto& Entry : LegacyDiskIndex)
			{
				const LegacyDiskIndexEntry& Record(Entry.second);
				if (Record.Location.IsFlagSet(LegacyDiskLocation::kStandaloneFile))
				{
					continue;
				}
				if (Record.Location.Offset() + Record.Location.Size() <= BlockFileSize)
				{
					continue;
				}
				ZEN_WARN("skipping invalid entry in '{}', reason: location is outside of file", LegacyLogPath);
				BadEntries.push_back(Entry.first);
			}
			for (const IoHash& BadHash : BadEntries)
			{
				LegacyDiskIndex.erase(BadHash);
			}
			InvalidEntryCount += BadEntries.size();
		}
	}
	if (InvalidEntryCount)
	{
		ZEN_WARN("found #{} invalid entries in '{}'", InvalidEntryCount, m_BucketDir / m_BucketName);
	}

	if (LegacyDiskIndex.empty())
	{
		LegacyCasLog.Close();
		BlockFile.Close();
		if (CleanSource)
		{
			// Older versions of ZenCacheDiskLayer expects the legacy files to exist if it can find
			// a manifest and crashes on startup if they don't.
			// In order to not break startup when switching back an older version, lets just reset
			// the legacy data files to zero length.

			BasicFile LegacyLog;
			LegacyLog.Open(LegacyLogPath, BasicFile::Mode::kTruncate);
			BasicFile LegacySobs;
			LegacySobs.Open(LegacyDataPath, BasicFile::Mode::kTruncate);
		}
		return 0;
	}

	uint64_t BlockChunkCount = 0;
	uint64_t BlockTotalSize	 = 0;
	for (const auto& Entry : LegacyDiskIndex)
	{
		const LegacyDiskIndexEntry& Record(Entry.second);
		if (Record.Location.IsFlagSet(LegacyDiskLocation::kStandaloneFile))
		{
			continue;
		}
		BlockChunkCount++;
		BlockTotalSize += Record.Location.Size();
	}

	uint64_t RequiredDiskSpace	   = BlockTotalSize + ((m_PayloadAlignment - 1) * BlockChunkCount);
	uint64_t MaxRequiredBlockCount = RoundUp(RequiredDiskSpace, MaxBlockSize) / MaxBlockSize;
	if (MaxRequiredBlockCount > BlockStoreDiskLocation::MaxBlockIndex)
	{
		ZEN_ERROR("legacy store migration from '{}' FAILED, required block count {}, possible {}",
				  m_BucketDir / m_BucketName,
				  MaxRequiredBlockCount,
				  BlockStoreDiskLocation::MaxBlockIndex);
		return 0;
	}

	constexpr const uint64_t DiskReserve = 1ul << 28;

	if (CleanSource)
	{
		if (Space.Free < (MaxBlockSize + DiskReserve))
		{
			ZEN_INFO("legacy store migration from '{}' aborted, not enough disk space available {} ({})",
					 m_BucketDir / m_BucketName,
					 NiceBytes(MaxBlockSize + DiskReserve),
					 NiceBytes(Space.Free));
			return 0;
		}
	}
	else
	{
		if (Space.Free < (RequiredDiskSpace + DiskReserve))
		{
			ZEN_INFO("legacy store migration from '{}' aborted, not enough disk space available {} ({})",
					 m_BucketDir / m_BucketName,
					 NiceBytes(RequiredDiskSpace + DiskReserve),
					 NiceBytes(Space.Free));
			return 0;
		}
	}

	std::filesystem::path LogPath = GetLogPath(m_BucketDir, m_BucketName);
	CreateDirectories(LogPath.parent_path());
	TCasLogFile<DiskIndexEntry> CasLog;
	CasLog.Open(LogPath, CasLogFile::Mode::kWrite);

	if (CleanSource && (MaxRequiredBlockCount < 2))
	{
		std::vector<DiskIndexEntry> LogEntries;
		LogEntries.reserve(LegacyDiskIndex.size());

		// We can use the block as is, just move it and add the blocks to our new log
		for (auto& Entry : LegacyDiskIndex)
		{
			const LegacyDiskIndexEntry& Record(Entry.second);

			DiskLocation NewLocation;
			uint8_t		 Flags = 0xff & (Record.Location.Flags() >> 56);
			if (Record.Location.IsFlagSet(LegacyDiskLocation::kStandaloneFile))
			{
				NewLocation = DiskLocation(Record.Location.Size(), Flags);
			}
			else
			{
				BlockStoreLocation NewChunkLocation(WriteBlockIndex, Record.Location.Offset(), Record.Location.Size());
				NewLocation = DiskLocation(NewChunkLocation, m_PayloadAlignment, Flags);
			}
			LogEntries.push_back({.Key = Entry.second.Key, .Location = NewLocation});
		}
		std::filesystem::path BlockPath = GetBlockPath(m_BlocksBasePath, WriteBlockIndex);
		CreateDirectories(BlockPath.parent_path());
		BlockFile.Close();
		std::filesystem::rename(LegacyDataPath, BlockPath);
		CasLog.Append(LogEntries);
		for (const DiskIndexEntry& Entry : LogEntries)
		{
			m_Index.insert_or_assign(Entry.Key, IndexEntry(Entry.Location, GcClock::TickCount()));
		}

		MigratedChunkCount += LogEntries.size();
		MigratedBlockCount++;
	}
	else
	{
		std::vector<IoHash> ChunkHashes;
		ChunkHashes.reserve(LegacyDiskIndex.size());
		for (const auto& Entry : LegacyDiskIndex)
		{
			ChunkHashes.push_back(Entry.first);
		}

		std::sort(begin(ChunkHashes), end(ChunkHashes), [&](IoHash Lhs, IoHash Rhs) {
			auto LhsKeyIt = LegacyDiskIndex.find(Lhs);
			auto RhsKeyIt = LegacyDiskIndex.find(Rhs);
			return LhsKeyIt->second.Location.Offset() < RhsKeyIt->second.Location.Offset();
		});

		uint64_t						BlockSize	= 0;
		uint64_t						BlockOffset = 0;
		std::vector<BlockStoreLocation> NewLocations;
		struct BlockData
		{
			std::vector<std::pair<IoHash, BlockStoreLocation>> Chunks;
			uint64_t										   BlockOffset;
			uint64_t										   BlockSize;
			uint32_t										   BlockIndex;
		};

		std::vector<BlockData>							   BlockRanges;
		std::vector<std::pair<IoHash, BlockStoreLocation>> Chunks;
		BlockRanges.reserve(MaxRequiredBlockCount);
		for (const IoHash& ChunkHash : ChunkHashes)
		{
			const LegacyDiskIndexEntry& LegacyEntry			= LegacyDiskIndex[ChunkHash];
			const LegacyDiskLocation&	LegacyChunkLocation = LegacyEntry.Location;

			if (LegacyChunkLocation.IsFlagSet(LegacyDiskLocation::kStandaloneFile))
			{
				// For standalone files we just store the chunk hash an use the size from the legacy index as is
				Chunks.push_back({ChunkHash, {}});
				continue;
			}

			uint64_t ChunkOffset = LegacyChunkLocation.Offset();
			uint64_t ChunkSize	 = LegacyChunkLocation.Size();
			uint64_t ChunkEnd	 = ChunkOffset + ChunkSize;

			if (BlockSize == 0)
			{
				BlockOffset = ChunkOffset;
			}
			if ((ChunkEnd - BlockOffset) > MaxBlockSize)
			{
				BlockData BlockRange{.BlockOffset = BlockOffset, .BlockSize = BlockSize, .BlockIndex = WriteBlockIndex};
				BlockRange.Chunks.swap(Chunks);
				BlockRanges.push_back(BlockRange);

				WriteBlockIndex++;
				while (std::filesystem::exists(GetBlockPath(m_BlocksBasePath, WriteBlockIndex)))
				{
					++WriteBlockIndex;
				}
				BlockOffset = ChunkOffset;
				BlockSize	= 0;
			}
			BlockSize						 = RoundUp(BlockSize, m_PayloadAlignment);
			BlockStoreLocation ChunkLocation = {.BlockIndex = WriteBlockIndex, .Offset = ChunkOffset - BlockOffset, .Size = ChunkSize};
			Chunks.push_back({ChunkHash, ChunkLocation});
			BlockSize = ChunkEnd - BlockOffset;
		}
		if (BlockSize > 0)
		{
			BlockRanges.push_back(
				{.Chunks = std::move(Chunks), .BlockOffset = BlockOffset, .BlockSize = BlockSize, .BlockIndex = WriteBlockIndex});
		}
		Stopwatch WriteBlockTimer;

		std::reverse(BlockRanges.begin(), BlockRanges.end());
		std::vector<std::uint8_t> Buffer(1 << 28);
		for (size_t Idx = 0; Idx < BlockRanges.size(); ++Idx)
		{
			const BlockData& BlockRange = BlockRanges[Idx];
			if (Idx > 0)
			{
				uint64_t Remaining = BlockRange.BlockOffset + BlockRange.BlockSize;
				uint64_t Completed = BlockOffset + BlockSize - Remaining;
				uint64_t ETA	   = (WriteBlockTimer.GetElapsedTimeMs() * Remaining) / Completed;

				ZEN_INFO("migrating store '{}' {}/{} blocks, remaining {} ({}) ETA: {}",
						 m_BucketDir / m_BucketDir,
						 Idx,
						 BlockRanges.size(),
						 NiceBytes(BlockRange.BlockOffset + BlockRange.BlockSize),
						 NiceBytes(BlockOffset + BlockSize),
						 NiceTimeSpanMs(ETA));
			}

			std::filesystem::path BlockPath = GetBlockPath(m_BlocksBasePath, BlockRange.BlockIndex);
			BlockStoreFile		  ChunkBlock(BlockPath);
			ChunkBlock.Create(BlockRange.BlockSize);
			uint64_t Offset = 0;
			while (Offset < BlockRange.BlockSize)
			{
				uint64_t Size = BlockRange.BlockSize - Offset;
				if (Size > Buffer.size())
				{
					Size = Buffer.size();
				}
				BlockFile.Read(Buffer.data(), Size, BlockRange.BlockOffset + Offset);
				ChunkBlock.Write(Buffer.data(), Size, Offset);
				Offset += Size;
			}
			ChunkBlock.Truncate(Offset);
			ChunkBlock.Flush();

			std::vector<DiskIndexEntry> LogEntries;
			LogEntries.reserve(BlockRange.Chunks.size());
			for (const auto& Entry : BlockRange.Chunks)
			{
				const LegacyDiskIndexEntry& LegacyEntry = LegacyDiskIndex[Entry.first];

				DiskLocation NewLocation;
				uint8_t		 Flags = 0xff & (LegacyEntry.Location.Flags() >> 56);
				if (LegacyEntry.Location.IsFlagSet(LegacyDiskLocation::kStandaloneFile))
				{
					NewLocation = DiskLocation(LegacyEntry.Location.Size(), Flags);
				}
				else
				{
					NewLocation = DiskLocation(Entry.second, m_PayloadAlignment, Flags);
				}
				LogEntries.push_back({.Key = Entry.first, .Location = NewLocation});
			}
			CasLog.Append(LogEntries);
			for (const DiskIndexEntry& Entry : LogEntries)
			{
				m_Index.insert_or_assign(Entry.Key, IndexEntry(Entry.Location, GcClock::TickCount()));
			}
			MigratedChunkCount += LogEntries.size();
			MigratedBlockCount++;

			if (CleanSource)
			{
				std::vector<LegacyDiskIndexEntry> LegacyLogEntries;
				LegacyLogEntries.reserve(BlockRange.Chunks.size());
				for (const auto& Entry : BlockRange.Chunks)
				{
					LegacyLogEntries.push_back(
						{.Key = Entry.first, .Location = LegacyDiskLocation(0, 0, 0, LegacyDiskLocation::kTombStone)});
				}
				LegacyCasLog.Append(LegacyLogEntries);
				BlockFile.SetFileSize(BlockRange.BlockOffset);
			}
		}
	}
	BlockFile.Close();
	LegacyCasLog.Close();
	CasLog.Close();

	if (CleanSource)
	{
		// Older versions of ZenCacheDiskLayer expects the legacy files to exist if it can find
		// a manifest and crashes on startup if they don't.
		// In order to not break startup when switching back an older version, lets just reset
		// the legacy data files to zero length.

		BasicFile LegacyLog;
		LegacyLog.Open(LegacyLogPath, BasicFile::Mode::kTruncate);
		BasicFile LegacySobs;
		LegacySobs.Open(LegacyDataPath, BasicFile::Mode::kTruncate);
	}
	return MigratedChunkCount;
}

void
ZenCacheDiskLayer::CacheBucket::OpenLog(const fs::path& BucketDir, const bool IsNew)
{
	m_BucketDir = BucketDir;

	m_TotalSize = 0;

	m_Index.clear();

	std::filesystem::path LegacyLogPath = GetLegacyLogPath(m_BucketDir);
	std::filesystem::path LogPath		= GetLogPath(m_BucketDir, m_BucketName);
	std::filesystem::path IndexPath		= GetIndexPath(m_BucketDir, m_BucketName);

	if (IsNew)
	{
		std::filesystem::path LegacyDataPath = GetLegacyDataPath(m_BucketDir);
		fs::remove(LegacyLogPath);
		fs::remove(LegacyDataPath);
		fs::remove(LogPath);
		fs::remove(IndexPath);
		fs::remove_all(m_BlocksBasePath);
	}

	uint64_t LogPosition		 = ReadIndexFile();
	uint64_t LogEntryCount		 = ReadLog(LogPosition);
	uint64_t LegacyLogEntryCount = MigrateLegacyData(true);

	CreateDirectories(m_BucketDir);

	m_SlogFile.Open(LogPath, CasLogFile::Mode::kWrite);

	std::unordered_set<uint32_t> KnownBlocks;
	for (const auto& Entry : m_Index)
	{
		const DiskLocation& Location = Entry.second.Location;
		m_TotalSize.fetch_add(Location.Size(), std::memory_order_seq_cst);
		if (Location.IsFlagSet(DiskLocation::kStandaloneFile))
		{
			continue;
		}
		KnownBlocks.insert(Location.GetBlockLocation(m_PayloadAlignment).BlockIndex);
	}

	if (std::filesystem::is_directory(m_BlocksBasePath))
	{
		std::vector<std::filesystem::path> FoldersToScan;
		FoldersToScan.push_back(m_BlocksBasePath);
		size_t FolderOffset = 0;
		while (FolderOffset < FoldersToScan.size())
		{
			for (const std::filesystem::directory_entry& Entry : std::filesystem::directory_iterator(FoldersToScan[FolderOffset]))
			{
				if (Entry.is_directory())
				{
					FoldersToScan.push_back(Entry.path());
					continue;
				}
				if (Entry.is_regular_file())
				{
					const std::filesystem::path Path = Entry.path();
					if (Path.extension() != DataExtension)
					{
						continue;
					}
					std::string FileName = Path.stem().string();
					uint32_t	BlockIndex;
					bool		OK = ParseHexNumber(FileName, BlockIndex);
					if (!OK)
					{
						continue;
					}
					if (!KnownBlocks.contains(BlockIndex))
					{
						// Log removing unreferenced block
						// Clear out unused blocks
						ZEN_INFO("removing unused block for '{}' at '{}'", m_BucketDir / m_BucketName, Path);
						std::error_code Ec;
						std::filesystem::remove(Path, Ec);
						if (Ec)
						{
							ZEN_WARN("Failed to delete file '{}' reason: '{}'", Path, Ec.message());
						}
						continue;
					}
					Ref<BlockStoreFile> BlockFile = new BlockStoreFile(Path);
					BlockFile->Open();
					m_ChunkBlocks[BlockIndex] = BlockFile;
				}
			}
			++FolderOffset;
		}
	}
	else
	{
		CreateDirectories(m_BlocksBasePath);
	}

	if (IsNew || ((LogEntryCount + LegacyLogEntryCount) > 0))
	{
		MakeIndexSnapshot();
	}
	// TODO: should validate integrity of container files here
}

void
ZenCacheDiskLayer::CacheBucket::BuildPath(PathBuilderBase& Path, const IoHash& HashKey)
{
	char HexString[sizeof(HashKey.Hash) * 2];
	ToHexBytes(HashKey.Hash, sizeof HashKey.Hash, HexString);

	Path.Append(m_BucketDir);
	Path.Append(L"/blob/");
	Path.AppendAsciiRange(HexString, HexString + 3);
	Path.AppendSeparator();
	Path.AppendAsciiRange(HexString + 3, HexString + 5);
	Path.AppendSeparator();
	Path.AppendAsciiRange(HexString + 5, HexString + sizeof(HexString));
}

bool
ZenCacheDiskLayer::CacheBucket::GetInlineCacheValue(const DiskLocation& Loc, ZenCacheValue& OutValue)
{
	if (Loc.IsFlagSet(DiskLocation::kStandaloneFile))
	{
		return false;
	}

	const BlockStoreLocation& Location	 = Loc.GetBlockLocation(m_PayloadAlignment);
	Ref<BlockStoreFile>		  ChunkBlock = m_ChunkBlocks[Location.BlockIndex];

	OutValue.Value = ChunkBlock->GetChunk(Location.Offset, Location.Size);
	OutValue.Value.SetContentType(Loc.GetContentType());

	return true;
}

bool
ZenCacheDiskLayer::CacheBucket::GetStandaloneCacheValue(const DiskLocation& Loc, const IoHash& HashKey, ZenCacheValue& OutValue)
{
	ExtendablePathBuilder<256> DataFilePath;
	BuildPath(DataFilePath, HashKey);

	RwLock::SharedLockScope ValueLock(LockForHash(HashKey));

	if (IoBuffer Data = IoBufferBuilder::MakeFromFile(DataFilePath.ToPath()))
	{
		OutValue.Value = Data;
		OutValue.Value.SetContentType(Loc.GetContentType());

		return true;
	}

	return false;
}

bool
ZenCacheDiskLayer::CacheBucket::Get(const IoHash& HashKey, ZenCacheValue& OutValue)
{
	if (!m_IsOk)
	{
		return false;
	}

	RwLock::SharedLockScope _(m_IndexLock);

	if (auto It = m_Index.find(HashKey); It != m_Index.end())
	{
		IndexEntry& Entry = It.value();
		Entry.LastAccess.store(GcClock::TickCount(), std::memory_order_relaxed);

		if (GetInlineCacheValue(Entry.Location, OutValue))
		{
			return true;
		}

		_.ReleaseNow();

		return GetStandaloneCacheValue(Entry.Location, HashKey, OutValue);
	}

	return false;
}

void
ZenCacheDiskLayer::CacheBucket::Put(const IoHash& HashKey, const ZenCacheValue& Value)
{
	if (!m_IsOk)
	{
		return;
	}

	if (Value.Value.Size() >= m_LargeObjectThreshold)
	{
		return PutStandaloneCacheValue(HashKey, Value);
	}

	// Small object put

	uint8_t EntryFlags = 0;

	if (Value.Value.GetContentType() == ZenContentType::kCbObject)
	{
		EntryFlags |= DiskLocation::kStructured;
	}
	else if (Value.Value.GetContentType() == ZenContentType::kCompressedBinary)
	{
		EntryFlags |= DiskLocation::kCompressed;
	}

	uint64_t ChunkSize = Value.Value.Size();

	uint32_t			WriteBlockIndex;
	Ref<BlockStoreFile> WriteBlock;
	uint64_t			InsertOffset;

	{
		RwLock::ExclusiveLockScope _(m_InsertLock);

		WriteBlockIndex = m_WriteBlockIndex.load(std::memory_order_acquire);
		bool IsWriting	= m_WriteBlock != nullptr;
		if (!IsWriting || (m_CurrentInsertOffset + ChunkSize) > MaxBlockSize)
		{
			if (m_WriteBlock)
			{
				m_WriteBlock = nullptr;
			}
			{
				RwLock::ExclusiveLockScope __(m_IndexLock);
				if (m_ChunkBlocks.size() == BlockStoreDiskLocation::MaxBlockIndex)
				{
					throw std::runtime_error(fmt::format("unable to allocate a new block in '{}'", m_BucketDir / m_BucketName));
				}
				WriteBlockIndex += IsWriting ? 1 : 0;
				while (m_ChunkBlocks.contains(WriteBlockIndex))
				{
					WriteBlockIndex = (WriteBlockIndex + 1) & BlockStoreDiskLocation::MaxBlockIndex;
				}
				std::filesystem::path BlockPath = GetBlockPath(m_BlocksBasePath, WriteBlockIndex);
				m_WriteBlock					= new BlockStoreFile(BlockPath);
				m_ChunkBlocks[WriteBlockIndex]	= m_WriteBlock;
				m_WriteBlockIndex.store(WriteBlockIndex, std::memory_order_release);
			}
			m_CurrentInsertOffset = 0;
			m_WriteBlock->Create(MaxBlockSize);
		}
		InsertOffset		  = m_CurrentInsertOffset;
		m_CurrentInsertOffset = RoundUp(InsertOffset + ChunkSize, m_PayloadAlignment);
		WriteBlock			  = m_WriteBlock;
	}

	DiskLocation Location({.BlockIndex = WriteBlockIndex, .Offset = InsertOffset, .Size = ChunkSize}, m_PayloadAlignment, EntryFlags);
	const DiskIndexEntry DiskIndexEntry{.Key = HashKey, .Location = Location};

	WriteBlock->Write(Value.Value.Data(), ChunkSize, InsertOffset);
	m_SlogFile.Append(DiskIndexEntry);

	m_TotalSize.fetch_add(ChunkSize, std::memory_order_seq_cst);
	{
		RwLock::ExclusiveLockScope __(m_IndexLock);
		if (auto It = m_Index.find(HashKey); It != m_Index.end())
		{
			// TODO: should check if write is idempotent and bail out if it is?
			// this would requiring comparing contents on disk unless we add a
			// content hash to the index entry
			IndexEntry& Entry = It.value();
			Entry.Location	  = Location;
			Entry.LastAccess.store(GcClock::TickCount(), std::memory_order_relaxed);
		}
		else
		{
			m_Index.insert({HashKey, {Location, GcClock::TickCount()}});
		}
	}
}

void
ZenCacheDiskLayer::CacheBucket::Drop()
{
	// TODO: close all open files and manage locking
	// TODO: add error handling
	m_SlogFile.Close();
	DeleteDirectories(m_BucketDir);
}

void
ZenCacheDiskLayer::CacheBucket::Flush()
{
	{
		RwLock::ExclusiveLockScope _(m_InsertLock);
		if (m_CurrentInsertOffset > 0)
		{
			uint32_t WriteBlockIndex = m_WriteBlockIndex.load(std::memory_order_acquire);
			WriteBlockIndex			 = (WriteBlockIndex + 1) & BlockStoreDiskLocation::MaxBlockIndex;
			m_WriteBlock			 = nullptr;
			m_WriteBlockIndex.store(WriteBlockIndex, std::memory_order_release);
			m_CurrentInsertOffset = 0;
		}
	}
	RwLock::SharedLockScope _(m_IndexLock);

	MakeIndexSnapshot();

	SaveManifest();
}

void
ZenCacheDiskLayer::CacheBucket::SaveManifest()
{
	using namespace std::literals;

	CbObjectWriter Writer;
	Writer << "BucketId"sv << m_BucketId;

	if (!m_Index.empty())
	{
		Writer.BeginArray("Timestamps"sv);
		for (auto& Kv : m_Index)
		{
			const IoHash&	  Key	= Kv.first;
			const IndexEntry& Entry = Kv.second;

			Writer.BeginObject();
			Writer << "Key"sv << Key;
			Writer << "LastAccess"sv << Entry.LastAccess;
			Writer.EndObject();
		}
		Writer.EndArray();
	}

	SaveCompactBinaryObject(m_BucketDir / "zen_manifest", Writer.Save());
}

void
ZenCacheDiskLayer::CacheBucket::Scrub(ScrubContext& Ctx)
{
	std::vector<IoHash> BadKeys;

	{
		RwLock::SharedLockScope _(m_IndexLock);

		for (auto& Kv : m_Index)
		{
			const IoHash&		HashKey = Kv.first;
			const DiskLocation& Loc		= Kv.second.Location;

			ZenCacheValue Value;

			if (GetInlineCacheValue(Loc, Value))
			{
				// Validate contents
			}
			else if (GetStandaloneCacheValue(Loc, HashKey, Value))
			{
				// Note: we cannot currently validate contents since we don't
				// have a content hash!
			}
			else
			{
				// Value not found
				BadKeys.push_back(HashKey);
			}
		}
	}

	if (BadKeys.empty())
	{
		return;
	}

	if (Ctx.RunRecovery())
	{
		RwLock::ExclusiveLockScope _(m_IndexLock);

		for (const IoHash& BadKey : BadKeys)
		{
			// Log a tombstone and delete the in-memory index for the bad entry

			const auto	 It		  = m_Index.find(BadKey);
			DiskLocation Location = It->second.Location;
			Location.Flags |= DiskLocation::kTombStone;
			m_SlogFile.Append(DiskIndexEntry{.Key = BadKey, .Location = Location});
			m_Index.erase(BadKey);
		}
	}
}

void
ZenCacheDiskLayer::CacheBucket::GatherReferences(GcContext& GcCtx)
{
	ZEN_TRACE_CPU("Z$::DiskLayer::CacheBucket::GatherReferences");

	uint64_t WriteBlockTimeUs		 = 0;
	uint64_t WriteBlockLongestTimeUs = 0;
	uint64_t ReadBlockTimeUs		 = 0;
	uint64_t ReadBlockLongestTimeUs	 = 0;

	Stopwatch  TotalTimer;
	const auto _ = MakeGuard([this, &TotalTimer, &WriteBlockTimeUs, &WriteBlockLongestTimeUs, &ReadBlockTimeUs, &ReadBlockLongestTimeUs] {
		ZEN_INFO("gathered references from '{}' in {} write lock: {} ({}), read lock: {} ({})",
				 m_BucketDir / m_BucketName,
				 NiceTimeSpanMs(TotalTimer.GetElapsedTimeMs()),
				 NiceLatencyNs(WriteBlockTimeUs),
				 NiceLatencyNs(WriteBlockLongestTimeUs),
				 NiceLatencyNs(ReadBlockTimeUs),
				 NiceLatencyNs(ReadBlockLongestTimeUs));
	});

	const GcClock::TimePoint ExpireTime =
		GcCtx.MaxCacheDuration() == GcClock::Duration::max() ? GcClock::TimePoint::min() : GcCtx.Time() - GcCtx.MaxCacheDuration();

	const GcClock::Tick ExpireTicks = ExpireTime.time_since_epoch().count();

	IndexMap Index;
	{
		RwLock::SharedLockScope __(m_IndexLock);
		Stopwatch				Timer;
		const auto				___ = MakeGuard([&Timer, &WriteBlockTimeUs, &WriteBlockLongestTimeUs] {
			 uint64_t ElapsedUs = Timer.GetElapsedTimeUs();
			 WriteBlockTimeUs += ElapsedUs;
			 WriteBlockLongestTimeUs = std::max(ElapsedUs, WriteBlockLongestTimeUs);
		 });
		Index						= m_Index;
	}

	std::vector<IoHash> ExpiredKeys;
	ExpiredKeys.reserve(1024);

	std::vector<IoHash> Cids;
	Cids.reserve(1024);

	for (const auto& Entry : Index)
	{
		const IoHash& Key = Entry.first;
		if (Entry.second.LastAccess < ExpireTicks)
		{
			ExpiredKeys.push_back(Key);
			continue;
		}

		const DiskLocation& Loc = Entry.second.Location;

		if (Loc.IsFlagSet(DiskLocation::kStructured))
		{
			if (Cids.size() > 1024)
			{
				GcCtx.ContributeCids(Cids);
				Cids.clear();
			}

			ZenCacheValue CacheValue;
			{
				RwLock::SharedLockScope __(m_IndexLock);
				Stopwatch				Timer;
				const auto				___ = MakeGuard([&Timer, &WriteBlockTimeUs, &WriteBlockLongestTimeUs] {
					 uint64_t ElapsedUs = Timer.GetElapsedTimeUs();
					 WriteBlockTimeUs += ElapsedUs;
					 WriteBlockLongestTimeUs = std::max(ElapsedUs, WriteBlockLongestTimeUs);
				 });
				if (!GetInlineCacheValue(Loc, CacheValue))
				{
					GetStandaloneCacheValue(Loc, Key, CacheValue);
				}
			}

			if (CacheValue.Value)
			{
				ZEN_ASSERT(CacheValue.Value.GetContentType() == ZenContentType::kCbObject);
				CbObject Obj(SharedBuffer{CacheValue.Value});
				Obj.IterateAttachments([&Cids](CbFieldView Field) { Cids.push_back(Field.AsAttachment()); });
			}
		}
	}

	GcCtx.ContributeCids(Cids);
	GcCtx.ContributeCacheKeys(m_BucketName, std::move(ExpiredKeys));
}

void
ZenCacheDiskLayer::CacheBucket::CollectGarbage(GcContext& GcCtx)
{
	ZEN_TRACE_CPU("Z$::DiskLayer::CacheBucket::CollectGarbage");

	std::vector<DiskIndexEntry> ExpiredStandaloneEntries;

	Stopwatch TotalTimer;
	uint64_t  WriteBlockTimeUs		  = 0;
	uint64_t  WriteBlockLongestTimeUs = 0;
	uint64_t  ReadBlockTimeUs		  = 0;
	uint64_t  ReadBlockLongestTimeUs  = 0;
	uint64_t  TotalChunkCount		  = 0;
	uint64_t  DeletedSize			  = 0;
	uint64_t  OldTotalSize			  = m_TotalSize.load(std::memory_order::relaxed);

	uint64_t DeletedCount = 0;
	uint64_t MovedCount	  = 0;

	const auto _ = MakeGuard([this,
							  &TotalTimer,
							  &WriteBlockTimeUs,
							  &WriteBlockLongestTimeUs,
							  &ReadBlockTimeUs,
							  &ReadBlockLongestTimeUs,
							  &TotalChunkCount,
							  &DeletedCount,
							  &MovedCount,
							  &DeletedSize,
							  &OldTotalSize] {
		ZEN_INFO(
			"garbage collect from '{}' DONE after {}, write lock: {} ({}), read lock: {} ({}), collected {} bytes, deleted #{} and moved "
			"#{} "
			"of #{} "
			"entires ({}).",
			m_BucketDir / m_BucketName,
			NiceTimeSpanMs(TotalTimer.GetElapsedTimeMs()),
			NiceLatencyNs(WriteBlockTimeUs),
			NiceLatencyNs(WriteBlockLongestTimeUs),
			NiceLatencyNs(ReadBlockTimeUs),
			NiceLatencyNs(ReadBlockLongestTimeUs),
			NiceBytes(DeletedSize),
			DeletedCount,
			MovedCount,
			TotalChunkCount,
			NiceBytes(OldTotalSize));
		RwLock::SharedLockScope _(m_IndexLock);
		SaveManifest();
	});

	m_SlogFile.Flush();

	IndexMap Index;
	size_t	 BlockCount;
	uint64_t ExcludeBlockIndex = 0x800000000ull;

	std::span<const IoHash> ExpiredCacheKeys = GcCtx.ExpiredCacheKeys(m_BucketName);
	std::vector<IoHash>		DeleteCacheKeys;
	DeleteCacheKeys.reserve(ExpiredCacheKeys.size());
	GcCtx.FilterCas(ExpiredCacheKeys, [&](const IoHash& ChunkHash, bool Keep) {
		if (Keep)
		{
			return;
		}
		DeleteCacheKeys.push_back(ChunkHash);
	});
	if (DeleteCacheKeys.empty())
	{
		ZEN_INFO("garbage collect SKIPPED, for '{}', no expired cache keys found", m_BucketDir / m_BucketName);
		return;
	}
	{
		RwLock::SharedLockScope __(m_InsertLock);
		RwLock::SharedLockScope ___(m_IndexLock);
		{
			Stopwatch  Timer;
			const auto ____ = MakeGuard([&Timer, &WriteBlockTimeUs, &WriteBlockLongestTimeUs] {
				uint64_t ElapsedUs = Timer.GetElapsedTimeUs();
				WriteBlockTimeUs += ElapsedUs;
				WriteBlockLongestTimeUs = std::max(ElapsedUs, WriteBlockLongestTimeUs);
			});
			if (m_Index.empty())
			{
				ZEN_INFO("garbage collect SKIPPED, for '{}', container is empty", m_BucketDir / m_BucketName);
				return;
			}
			if (m_WriteBlock)
			{
				ExcludeBlockIndex = m_WriteBlockIndex.load(std::memory_order_acquire);
			}
			__.ReleaseNow();
		}
		SaveManifest();
		Index	   = m_Index;
		BlockCount = m_ChunkBlocks.size();

		for (const IoHash& Key : DeleteCacheKeys)
		{
			if (auto It = Index.find(Key); It != Index.end())
			{
				DiskIndexEntry Entry = {.Key = It->first, .Location = It->second.Location};
				if (Entry.Location.Flags & DiskLocation::kStandaloneFile)
				{
					Entry.Location.Flags |= DiskLocation::kTombStone;
					ExpiredStandaloneEntries.push_back(Entry);
				}
			}
		}
		if (GcCtx.IsDeletionMode())
		{
			for (const auto& Entry : ExpiredStandaloneEntries)
			{
				m_Index.erase(Entry.Key);
			}
			m_SlogFile.Append(ExpiredStandaloneEntries);
		}
	}

	if (GcCtx.IsDeletionMode())
	{
		std::error_code			   Ec;
		ExtendablePathBuilder<256> Path;

		for (const auto& Entry : ExpiredStandaloneEntries)
		{
			const IoHash&		Key = Entry.Key;
			const DiskLocation& Loc = Entry.Location;

			Path.Reset();
			BuildPath(Path, Key);

			{
				RwLock::SharedLockScope __(m_IndexLock);
				if (m_Index.contains(Key))
				{
					// Someone added it back, let the file on disk be
					ZEN_DEBUG("skipping z$ delete standalone of file '{}' FAILED, it has been added back", Path.ToUtf8());
					continue;
				}
				ZEN_DEBUG("deleting standalone cache file '{}'", Path.ToUtf8());
				fs::remove(Path.c_str(), Ec);
			}

			if (Ec)
			{
				ZEN_WARN("delete expired z$ standalone file '{}' FAILED, reason: '{}'", Path.ToUtf8(), Ec.message());
				Ec.clear();
				DiskLocation RestoreLocation = Loc;
				RestoreLocation.Flags &= ~DiskLocation::kTombStone;

				RwLock::ExclusiveLockScope __(m_IndexLock);
				Stopwatch				   Timer;
				const auto				   ___ = MakeGuard([&Timer, &ReadBlockTimeUs, &ReadBlockLongestTimeUs] {
					uint64_t ElapsedUs = Timer.GetElapsedTimeUs();
					ReadBlockTimeUs += ElapsedUs;
					ReadBlockLongestTimeUs = std::max(ElapsedUs, ReadBlockLongestTimeUs);
				});
				if (m_Index.contains(Key))
				{
					continue;
				}
				m_SlogFile.Append(DiskIndexEntry{.Key = Key, .Location = RestoreLocation});
				m_Index.insert({Key, {Loc, GcClock::TickCount()}});
				m_TotalSize.fetch_add(Entry.Location.Size(), std::memory_order_seq_cst);
				continue;
			}
			m_TotalSize.fetch_sub(Entry.Location.Size(), std::memory_order_seq_cst);
			DeletedSize += Entry.Location.Size();
			DeletedCount++;
		}
	}

	TotalChunkCount = Index.size();

	std::vector<IoHash> TotalChunkHashes;
	TotalChunkHashes.reserve(TotalChunkCount);
	for (const auto& Entry : Index)
	{
		const DiskLocation& Location = Entry.second.Location;

		if (Location.Flags & DiskLocation::kStandaloneFile)
		{
			continue;
		}
		TotalChunkHashes.push_back(Entry.first);
	}

	if (TotalChunkHashes.empty())
	{
		return;
	}
	std::unordered_map<uint32_t, size_t> BlockIndexToChunkMapIndex;
	std::vector<std::vector<IoHash>>	 KeepChunks;
	std::vector<std::vector<IoHash>>	 DeleteChunks;

	BlockIndexToChunkMapIndex.reserve(BlockCount);
	KeepChunks.reserve(BlockCount);
	DeleteChunks.reserve(BlockCount);
	size_t GuesstimateCountPerBlock = TotalChunkHashes.size() / BlockCount / 2;

	uint64_t DeleteCount = 0;

	uint64_t NewTotalSize = 0;

	std::unordered_set<IoHash, IoHash::Hasher> Expired;
	Expired.insert(DeleteCacheKeys.begin(), DeleteCacheKeys.end());

	GcCtx.FilterCas(TotalChunkHashes, [&](const IoHash& ChunkHash, bool Keep) {
		auto				KeyIt		  = Index.find(ChunkHash);
		const DiskLocation& Location	  = KeyIt->second.Location;
		BlockStoreLocation	BlockLocation = Location.GetBlockLocation(m_PayloadAlignment);

		uint32_t BlockIndex = BlockLocation.BlockIndex;

		if (static_cast<uint64_t>(BlockIndex) == ExcludeBlockIndex)
		{
			return;
		}

		auto   BlockIndexPtr = BlockIndexToChunkMapIndex.find(BlockIndex);
		size_t ChunkMapIndex = 0;
		if (BlockIndexPtr == BlockIndexToChunkMapIndex.end())
		{
			ChunkMapIndex						  = KeepChunks.size();
			BlockIndexToChunkMapIndex[BlockIndex] = ChunkMapIndex;
			KeepChunks.resize(ChunkMapIndex + 1);
			KeepChunks.back().reserve(GuesstimateCountPerBlock);
			DeleteChunks.resize(ChunkMapIndex + 1);
			DeleteChunks.back().reserve(GuesstimateCountPerBlock);
		}
		else
		{
			ChunkMapIndex = BlockIndexPtr->second;
		}
		if (Keep)
		{
			std::vector<IoHash>& ChunkMap = KeepChunks[ChunkMapIndex];
			ChunkMap.push_back(ChunkHash);
			NewTotalSize += BlockLocation.Size;
		}
		else
		{
			std::vector<IoHash>& ChunkMap = DeleteChunks[ChunkMapIndex];
			ChunkMap.push_back(ChunkHash);
			DeleteCount++;
		}
	});

	std::unordered_set<uint32_t> BlocksToReWrite;
	BlocksToReWrite.reserve(BlockIndexToChunkMapIndex.size());
	for (const auto& Entry : BlockIndexToChunkMapIndex)
	{
		uint32_t				   BlockIndex	 = Entry.first;
		size_t					   ChunkMapIndex = Entry.second;
		const std::vector<IoHash>& ChunkMap		 = DeleteChunks[ChunkMapIndex];
		if (ChunkMap.empty())
		{
			continue;
		}
		BlocksToReWrite.insert(BlockIndex);
	}

	const bool PerformDelete = GcCtx.IsDeletionMode() && GcCtx.CollectSmallObjects();
	if (!PerformDelete)
	{
		uint64_t TotalSize = m_TotalSize.load(std::memory_order_relaxed);
		ZEN_INFO("garbage collect from '{}' DISABLED, found #{} {} chunks of total #{} {}",
				 m_BucketDir / m_BucketName,
				 DeleteCount,
				 NiceBytes(TotalSize - NewTotalSize),
				 TotalChunkCount,
				 NiceBytes(TotalSize));
		return;
	}

	auto AddToDeleted = [this, &Index, &DeletedCount, &DeletedSize](const std::vector<IoHash>& DeletedEntries) {
		for (const IoHash& ChunkHash : DeletedEntries)
		{
			const DiskLocation& Location = Index[ChunkHash].Location;
			ZEN_ASSERT(!Location.IsFlagSet(DiskLocation::kStandaloneFile));
			DeletedSize += Index[ChunkHash].Location.GetBlockLocation(m_PayloadAlignment).Size;
		}
		DeletedCount += DeletedEntries.size();
	};

	// Move all chunks in blocks that have chunks removed to new blocks

	Ref<BlockStoreFile> NewBlockFile;
	uint64_t			WriteOffset	  = 0;
	uint32_t			NewBlockIndex = 0;

	auto UpdateLocations = [this](const std::span<DiskIndexEntry>& Entries) {
		for (const DiskIndexEntry& Entry : Entries)
		{
			if (Entry.Location.IsFlagSet(DiskLocation::kTombStone))
			{
				auto	 KeyIt	   = m_Index.find(Entry.Key);
				uint64_t ChunkSize = KeyIt->second.Location.GetBlockLocation(m_PayloadAlignment).Size;
				m_TotalSize.fetch_sub(ChunkSize, std::memory_order_seq_cst);
				m_Index.erase(KeyIt);
				continue;
			}
			m_Index[Entry.Key].Location = Entry.Location;
		}
	};

	std::unordered_map<IoHash, DiskLocation> MovedBlockChunks;
	for (uint32_t BlockIndex : BlocksToReWrite)
	{
		const size_t ChunkMapIndex = BlockIndexToChunkMapIndex[BlockIndex];

		Ref<BlockStoreFile> OldBlockFile;
		{
			RwLock::SharedLockScope _i(m_IndexLock);
			OldBlockFile = m_ChunkBlocks[BlockIndex];
		}

		const std::vector<IoHash>& KeepMap = KeepChunks[ChunkMapIndex];
		if (KeepMap.empty())
		{
			const std::vector<IoHash>&	DeleteMap  = DeleteChunks[ChunkMapIndex];
			std::vector<DiskIndexEntry> LogEntries = MakeDiskIndexEntries({}, DeleteMap);
			m_SlogFile.Append(LogEntries);
			m_SlogFile.Flush();
			{
				RwLock::ExclusiveLockScope _i(m_IndexLock);
				Stopwatch				   Timer;
				const auto				   __ = MakeGuard([&Timer, &ReadBlockTimeUs, &ReadBlockLongestTimeUs] {
					uint64_t ElapsedUs = Timer.GetElapsedTimeUs();
					ReadBlockTimeUs += ElapsedUs;
					ReadBlockLongestTimeUs = std::max(ElapsedUs, ReadBlockLongestTimeUs);
				});
				UpdateLocations(LogEntries);
				m_ChunkBlocks[BlockIndex] = nullptr;
			}
			AddToDeleted(DeleteMap);
			ZEN_DEBUG("marking cas store file for delete '{}', block #{}, '{}'",
					  m_BucketDir / m_BucketName,
					  BlockIndex,
					  OldBlockFile->GetPath());
			std::error_code Ec;
			OldBlockFile->MarkAsDeleteOnClose(Ec);
			if (Ec)
			{
				ZEN_WARN("Failed to flag file '{}' for deletion, reason: '{}'", OldBlockFile->GetPath(), Ec.message());
			}
			continue;
		}

		std::vector<uint8_t> Chunk;
		for (const IoHash& ChunkHash : KeepMap)
		{
			auto					 KeyIt		   = Index.find(ChunkHash);
			const BlockStoreLocation ChunkLocation = KeyIt->second.Location.GetBlockLocation(m_PayloadAlignment);
			Chunk.resize(ChunkLocation.Size);
			OldBlockFile->Read(Chunk.data(), Chunk.size(), ChunkLocation.Offset);

			if (!NewBlockFile || (WriteOffset + Chunk.size() > MaxBlockSize))
			{
				uint32_t					NextBlockIndex = m_WriteBlockIndex.load(std::memory_order_relaxed);
				std::vector<DiskIndexEntry> LogEntries	   = MakeDiskIndexEntries(MovedBlockChunks, {});
				m_SlogFile.Append(LogEntries);
				m_SlogFile.Flush();

				if (NewBlockFile)
				{
					NewBlockFile->Truncate(WriteOffset);
					NewBlockFile->Flush();
				}
				{
					RwLock::ExclusiveLockScope __(m_IndexLock);
					Stopwatch				   Timer;
					const auto				   ___ = MakeGuard([&Timer, &ReadBlockTimeUs, &ReadBlockLongestTimeUs] {
						uint64_t ElapsedUs = Timer.GetElapsedTimeUs();
						ReadBlockTimeUs += ElapsedUs;
						ReadBlockLongestTimeUs = std::max(ElapsedUs, ReadBlockLongestTimeUs);
					});
					UpdateLocations(LogEntries);
					if (m_ChunkBlocks.size() == BlockStoreDiskLocation::MaxBlockIndex)
					{
						ZEN_ERROR("unable to allocate a new block in '{}', count limit {} exeeded",
								  m_BucketDir / m_BucketName,
								  static_cast<uint64_t>(std::numeric_limits<uint32_t>::max()) + 1);
						return;
					}
					while (m_ChunkBlocks.contains(NextBlockIndex))
					{
						NextBlockIndex = (NextBlockIndex + 1) & BlockStoreDiskLocation::MaxBlockIndex;
					}
					std::filesystem::path NewBlockPath = GetBlockPath(m_BlocksBasePath, NextBlockIndex);
					NewBlockFile					   = new BlockStoreFile(NewBlockPath);
					m_ChunkBlocks[NextBlockIndex]	   = NewBlockFile;
				}

				MovedCount += MovedBlockChunks.size();
				MovedBlockChunks.clear();

				std::error_code Error;
				DiskSpace		Space = DiskSpaceInfo(m_BucketDir, Error);
				if (Error)
				{
					ZEN_ERROR("get disk space in '{}' FAILED, reason: '{}'", m_BucketDir, Error.message());
					return;
				}
				if (Space.Free < MaxBlockSize)
				{
					uint64_t ReclaimedSpace = GcCtx.ClaimGCReserve();
					if (Space.Free + ReclaimedSpace < MaxBlockSize)
					{
						ZEN_WARN("garbage collect from '{}' FAILED, required disk space {}, free {}",
								 m_BucketDir / m_BucketName,
								 MaxBlockSize,
								 NiceBytes(Space.Free + ReclaimedSpace));
						RwLock::ExclusiveLockScope _l(m_IndexLock);
						Stopwatch				   Timer;
						const auto				   __ = MakeGuard([&Timer, &ReadBlockTimeUs, &ReadBlockLongestTimeUs] {
							uint64_t ElapsedUs = Timer.GetElapsedTimeUs();
							ReadBlockTimeUs += ElapsedUs;
							ReadBlockLongestTimeUs = std::max(ElapsedUs, ReadBlockLongestTimeUs);
						});
						m_ChunkBlocks.erase(NextBlockIndex);
						return;
					}

					ZEN_INFO("using gc reserve for '{}', reclaimed {}, disk free {}",
							 m_BucketDir / m_BucketName,
							 ReclaimedSpace,
							 NiceBytes(Space.Free + ReclaimedSpace));
				}
				NewBlockFile->Create(MaxBlockSize);
				NewBlockIndex = NextBlockIndex;
				WriteOffset	  = 0;
			}

			NewBlockFile->Write(Chunk.data(), Chunk.size(), WriteOffset);
			MovedBlockChunks.emplace(ChunkHash,
									 DiskLocation({.BlockIndex = NewBlockIndex, .Offset = WriteOffset, .Size = Chunk.size()},
												  m_PayloadAlignment,
												  KeyIt->second.Location.Flags));
			WriteOffset = RoundUp(WriteOffset + Chunk.size(), m_PayloadAlignment);
		}
		Chunk.clear();
		if (NewBlockFile)
		{
			NewBlockFile->Truncate(WriteOffset);
			NewBlockFile->Flush();
			NewBlockFile = {};
		}

		const std::vector<IoHash>&	DeleteMap  = DeleteChunks[ChunkMapIndex];
		std::vector<DiskIndexEntry> LogEntries = MakeDiskIndexEntries(MovedBlockChunks, DeleteMap);
		m_SlogFile.Append(LogEntries);
		m_SlogFile.Flush();
		{
			RwLock::ExclusiveLockScope __(m_IndexLock);
			Stopwatch				   Timer;
			const auto				   ___ = MakeGuard([&Timer, &ReadBlockTimeUs, &ReadBlockLongestTimeUs] {
				uint64_t ElapsedUs = Timer.GetElapsedTimeUs();
				ReadBlockTimeUs += ElapsedUs;
				ReadBlockLongestTimeUs = std::max(ElapsedUs, ReadBlockLongestTimeUs);
			});
			UpdateLocations(LogEntries);
			m_ChunkBlocks[BlockIndex] = nullptr;
		}
		MovedCount += MovedBlockChunks.size();
		AddToDeleted(DeleteMap);
		MovedBlockChunks.clear();

		ZEN_DEBUG("marking cas store file for delete '{}', block #{}, '{}'",
				  m_BucketDir / m_BucketName,
				  BlockIndex,
				  OldBlockFile->GetPath());
		std::error_code Ec;
		OldBlockFile->MarkAsDeleteOnClose(Ec);
		if (Ec)
		{
			ZEN_WARN("Failed to flag file '{}' for deletion: '{}'", OldBlockFile->GetPath(), Ec.message());
		}
		OldBlockFile = nullptr;
	}
}

void
ZenCacheDiskLayer::CacheBucket::UpdateAccessTimes(const std::vector<zen::access_tracking::KeyAccessTime>& AccessTimes)
{
	using namespace access_tracking;

	for (const KeyAccessTime& KeyTime : AccessTimes)
	{
		if (auto It = m_Index.find(KeyTime.Key); It != m_Index.end())
		{
			IndexEntry& Entry = It.value();
			Entry.LastAccess.store(KeyTime.LastAccess, std::memory_order_relaxed);
		}
	}
}

void
ZenCacheDiskLayer::CollectGarbage(GcContext& GcCtx)
{
	RwLock::SharedLockScope _(m_Lock);

	for (auto& Kv : m_Buckets)
	{
		Kv.second.CollectGarbage(GcCtx);
	}
}

void
ZenCacheDiskLayer::UpdateAccessTimes(const zen::access_tracking::AccessTimes& AccessTimes)
{
	RwLock::SharedLockScope _(m_Lock);

	for (const auto& Kv : AccessTimes.Buckets)
	{
		if (auto It = m_Buckets.find(Kv.first); It != m_Buckets.end())
		{
			CacheBucket& Bucket = It->second;
			Bucket.UpdateAccessTimes(Kv.second);
		}
	}
}

void
ZenCacheDiskLayer::CacheBucket::PutStandaloneCacheValue(const IoHash& HashKey, const ZenCacheValue& Value)
{
	RwLock::ExclusiveLockScope ValueLock(LockForHash(HashKey));

	ExtendablePathBuilder<256> DataFilePath;
	BuildPath(DataFilePath, HashKey);

	TemporaryFile DataFile;

	std::error_code Ec;
	DataFile.CreateTemporary(m_BucketDir.c_str(), Ec);

	if (Ec)
	{
		throw std::system_error(Ec, fmt::format("Failed to open temporary file for put at '{}'", m_BucketDir));
	}

	DataFile.WriteAll(Value.Value, Ec);

	if (Ec)
	{
		throw std::system_error(Ec, fmt::format("Failed to write payload ({} bytes) to file", NiceBytes(Value.Value.Size())));
	}

	// Move file into place (atomically)

	std::filesystem::path FsPath{DataFilePath.ToPath()};

	DataFile.MoveTemporaryIntoPlace(FsPath, Ec);

	if (Ec)
	{
		int RetryCount = 3;

		do
		{
			std::filesystem::path ParentPath = FsPath.parent_path();
			CreateDirectories(ParentPath);

			DataFile.MoveTemporaryIntoPlace(FsPath, Ec);

			if (!Ec)
			{
				break;
			}

			std::error_code InnerEc;
			const uint64_t	ExistingFileSize = std::filesystem::file_size(FsPath, InnerEc);

			if (!InnerEc && ExistingFileSize == Value.Value.Size())
			{
				// Concurrent write of same value?
				return;
			}

			// Semi arbitrary back-off
			zen::Sleep(1000 * RetryCount);
		} while (RetryCount--);

		if (Ec)
		{
			throw std::system_error(Ec, fmt::format("Failed to finalize file '{}'", DataFilePath.ToUtf8()));
		}
	}

	// Update index

	uint8_t EntryFlags = DiskLocation::kStandaloneFile;

	if (Value.Value.GetContentType() == ZenContentType::kCbObject)
	{
		EntryFlags |= DiskLocation::kStructured;
	}
	else if (Value.Value.GetContentType() == ZenContentType::kCompressedBinary)
	{
		EntryFlags |= DiskLocation::kCompressed;
	}

	RwLock::ExclusiveLockScope _(m_IndexLock);

	DiskLocation Loc(Value.Value.Size(), EntryFlags);
	IndexEntry	 Entry = IndexEntry(Loc, GcClock::TickCount());

	if (auto It = m_Index.find(HashKey); It == m_Index.end())
	{
		// Previously unknown object
		m_Index.insert({HashKey, Entry});
	}
	else
	{
		// TODO: should check if write is idempotent and bail out if it is?
		It.value() = Entry;
	}

	m_SlogFile.Append({.Key = HashKey, .Location = Loc});
	m_TotalSize.fetch_add(Loc.Size(), std::memory_order_seq_cst);
}

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

ZenCacheDiskLayer::ZenCacheDiskLayer(const std::filesystem::path& RootDir) : m_RootDir(RootDir)
{
}

ZenCacheDiskLayer::~ZenCacheDiskLayer() = default;

bool
ZenCacheDiskLayer::Get(std::string_view InBucket, const IoHash& HashKey, ZenCacheValue& OutValue)
{
	const auto	 BucketName = std::string(InBucket);
	CacheBucket* Bucket		= nullptr;

	{
		RwLock::SharedLockScope _(m_Lock);

		auto it = m_Buckets.find(BucketName);

		if (it != m_Buckets.end())
		{
			Bucket = &it->second;
		}
	}

	if (Bucket == nullptr)
	{
		// Bucket needs to be opened/created

		RwLock::ExclusiveLockScope _(m_Lock);

		if (auto it = m_Buckets.find(BucketName); it != m_Buckets.end())
		{
			Bucket = &it->second;
		}
		else
		{
			auto It = m_Buckets.try_emplace(BucketName, BucketName);
			Bucket	= &It.first->second;

			std::filesystem::path BucketPath = m_RootDir;
			BucketPath /= BucketName;

			Bucket->OpenOrCreate(BucketPath);
		}
	}

	ZEN_ASSERT(Bucket != nullptr);

	return Bucket->Get(HashKey, OutValue);
}

void
ZenCacheDiskLayer::Put(std::string_view InBucket, const IoHash& HashKey, const ZenCacheValue& Value)
{
	const auto	 BucketName = std::string(InBucket);
	CacheBucket* Bucket		= nullptr;

	{
		RwLock::SharedLockScope _(m_Lock);

		auto it = m_Buckets.find(BucketName);

		if (it != m_Buckets.end())
		{
			Bucket = &it->second;
		}
	}

	if (Bucket == nullptr)
	{
		// New bucket needs to be created

		RwLock::ExclusiveLockScope _(m_Lock);

		if (auto it = m_Buckets.find(BucketName); it != m_Buckets.end())
		{
			Bucket = &it->second;
		}
		else
		{
			auto It = m_Buckets.try_emplace(BucketName, BucketName);
			Bucket	= &It.first->second;

			std::filesystem::path BucketPath = m_RootDir;
			BucketPath /= BucketName;

			Bucket->OpenOrCreate(BucketPath);
		}
	}

	ZEN_ASSERT(Bucket != nullptr);

	if (Bucket->IsOk())
	{
		Bucket->Put(HashKey, Value);
	}
}

void
ZenCacheDiskLayer::DiscoverBuckets()
{
	FileSystemTraversal Traversal;
	struct Visitor : public FileSystemTraversal::TreeVisitor
	{
		virtual void VisitFile([[maybe_unused]] const std::filesystem::path& Parent,
							   [[maybe_unused]] const path_view&			 File,
							   [[maybe_unused]] uint64_t					 FileSize) override
		{
		}

		virtual bool VisitDirectory([[maybe_unused]] const std::filesystem::path& Parent, const path_view& DirectoryName) override
		{
			Dirs.push_back((decltype(Dirs)::value_type)(DirectoryName));
			return false;
		}

		std::vector<std::filesystem::path::string_type> Dirs;
	} Visit;

	Traversal.TraverseFileSystem(m_RootDir, Visit);

	// Initialize buckets

	RwLock::ExclusiveLockScope _(m_Lock);

	for (const auto& BucketName : Visit.Dirs)
	{
		// New bucket needs to be created

#if ZEN_PLATFORM_WINDOWS
		std::string BucketName8 = WideToUtf8(BucketName);
#else
		const auto& BucketName8 = BucketName;
#endif

		if (auto It = m_Buckets.find(BucketName8); It != m_Buckets.end())
		{
		}
		else
		{
			auto InsertResult = m_Buckets.try_emplace(BucketName8, BucketName8);

			std::filesystem::path BucketPath = m_RootDir;
			BucketPath /= BucketName8;

			CacheBucket& Bucket = InsertResult.first->second;

			Bucket.OpenOrCreate(BucketPath, /* AllowCreate */ false);

			if (Bucket.IsOk())
			{
				ZEN_INFO("Discovered bucket '{}'", BucketName8);
			}
			else
			{
				ZEN_WARN("Found directory '{}' in our base directory '{}' but it is not a valid bucket", BucketName8, m_RootDir);

				m_Buckets.erase(InsertResult.first);
			}
		}
	}
}

bool
ZenCacheDiskLayer::DropBucket(std::string_view InBucket)
{
	RwLock::ExclusiveLockScope _(m_Lock);

	auto it = m_Buckets.find(std::string(InBucket));

	if (it != m_Buckets.end())
	{
		CacheBucket* Bucket = &it->second;

		Bucket->Drop();

		m_Buckets.erase(it);

		return true;
	}

	std::filesystem::path BucketPath = m_RootDir;
	BucketPath /= std::string(InBucket);

	return CacheBucket::Delete(BucketPath);
}

void
ZenCacheDiskLayer::Flush()
{
	std::vector<CacheBucket*> Buckets;

	{
		RwLock::SharedLockScope _(m_Lock);

		Buckets.reserve(m_Buckets.size());
		for (auto& Kv : m_Buckets)
		{
			Buckets.push_back(&Kv.second);
		}
	}

	for (auto& Bucket : Buckets)
	{
		Bucket->Flush();
	}
}

void
ZenCacheDiskLayer::Scrub(ScrubContext& Ctx)
{
	RwLock::SharedLockScope _(m_Lock);

	for (auto& Kv : m_Buckets)
	{
		Kv.second.Scrub(Ctx);
	}
}

void
ZenCacheDiskLayer::GatherReferences(GcContext& GcCtx)
{
	RwLock::SharedLockScope _(m_Lock);

	for (auto& Kv : m_Buckets)
	{
		Kv.second.GatherReferences(GcCtx);
	}
}

uint64_t
ZenCacheDiskLayer::TotalSize() const
{
	uint64_t				TotalSize{};
	RwLock::SharedLockScope _(m_Lock);

	for (auto& Kv : m_Buckets)
	{
		TotalSize += Kv.second.TotalSize();
	}

	return TotalSize;
}

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

#if ZEN_WITH_TESTS
}

namespace zen {

using namespace std::literals;

namespace testutils {
	IoHash CreateKey(size_t KeyValue) { return IoHash::HashBuffer(&KeyValue, sizeof(size_t)); }

	IoBuffer CreateBinaryCacheValue(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);

		IoBuffer Buf(IoBuffer::Clone, Values.data(), Values.size());
		Buf.SetContentType(ZenContentType::kBinary);
		return Buf;
	};

}  // namespace testutils

TEST_CASE("z$.store")
{
	ScopedTemporaryDirectory TempDir;

	CasGc Gc;

	ZenCacheStore Zcs(Gc, TempDir.Path() / "cache");

	const int kIterationCount = 100;

	for (int i = 0; i < kIterationCount; ++i)
	{
		const IoHash Key = IoHash::HashBuffer(&i, sizeof i);

		CbObjectWriter Cbo;
		Cbo << "hey" << i;
		CbObject Obj = Cbo.Save();

		ZenCacheValue Value;
		Value.Value = Obj.GetBuffer().AsIoBuffer();
		Value.Value.SetContentType(ZenContentType::kCbObject);

		Zcs.Put("test_bucket"sv, Key, Value);
	}

	for (int i = 0; i < kIterationCount; ++i)
	{
		const IoHash Key = IoHash::HashBuffer(&i, sizeof i);

		ZenCacheValue Value;
		Zcs.Get("test_bucket"sv, Key, /* out */ Value);

		REQUIRE(Value.Value);
		CHECK(Value.Value.GetContentType() == ZenContentType::kCbObject);
		CHECK_EQ(ValidateCompactBinary(Value.Value, CbValidateMode::All), CbValidateError::None);
		CbObject Obj = LoadCompactBinaryObject(Value.Value);
		CHECK_EQ(Obj["hey"].AsInt32(), i);
	}
}

TEST_CASE("z$.size")
{
	const auto CreateCacheValue = [](size_t Size) -> CbObject {
		std::vector<uint8_t> Buf;
		Buf.resize(Size);

		CbObjectWriter Writer;
		Writer.AddBinary("Binary"sv, Buf.data(), Buf.size());
		return Writer.Save();
	};

	SUBCASE("mem/disklayer")
	{
		const size_t			 Count = 16;
		ScopedTemporaryDirectory TempDir;

		GcStorageSize CacheSize;

		{
			CasGc		  Gc;
			ZenCacheStore Zcs(Gc, TempDir.Path() / "cache");

			CbObject CacheValue = CreateCacheValue(Zcs.DiskLayerThreshold() - 256);

			IoBuffer Buffer = CacheValue.GetBuffer().AsIoBuffer();
			Buffer.SetContentType(ZenContentType::kCbObject);

			for (size_t Key = 0; Key < Count; ++Key)
			{
				const size_t Bucket = Key % 4;
				Zcs.Put(fmt::format("test_bucket-{}", Bucket), IoHash::HashBuffer(&Key, sizeof(uint32_t)), {.Value = Buffer});
			}

			CacheSize = Zcs.StorageSize();
			CHECK_EQ(CacheValue.GetSize() * Count, CacheSize.DiskSize);
			CHECK_EQ(CacheValue.GetSize() * Count, CacheSize.MemorySize);
		}

		{
			CasGc		  Gc;
			ZenCacheStore Zcs(Gc, TempDir.Path() / "cache");

			const GcStorageSize SerializedSize = Zcs.StorageSize();
			CHECK_EQ(SerializedSize.MemorySize, 0);
			CHECK_EQ(SerializedSize.DiskSize, CacheSize.DiskSize);

			for (size_t Bucket = 0; Bucket < 4; ++Bucket)
			{
				Zcs.DropBucket(fmt::format("test_bucket-{}", Bucket));
			}
			CHECK_EQ(0, Zcs.StorageSize().DiskSize);
		}
	}

	SUBCASE("disklayer")
	{
		const size_t			 Count = 16;
		ScopedTemporaryDirectory TempDir;

		GcStorageSize CacheSize;

		{
			CasGc		  Gc;
			ZenCacheStore Zcs(Gc, TempDir.Path() / "cache");

			CbObject CacheValue = CreateCacheValue(Zcs.DiskLayerThreshold() + 64);

			IoBuffer Buffer = CacheValue.GetBuffer().AsIoBuffer();
			Buffer.SetContentType(ZenContentType::kCbObject);

			for (size_t Key = 0; Key < Count; ++Key)
			{
				const size_t Bucket = Key % 4;
				Zcs.Put(fmt::format("test_bucket-{}", Bucket), IoHash::HashBuffer(&Key, sizeof(uint32_t)), {.Value = Buffer});
			}

			CacheSize = Zcs.StorageSize();
			CHECK_EQ(CacheValue.GetSize() * Count, CacheSize.DiskSize);
			CHECK_EQ(0, CacheSize.MemorySize);
		}

		{
			CasGc		  Gc;
			ZenCacheStore Zcs(Gc, TempDir.Path() / "cache");

			const GcStorageSize SerializedSize = Zcs.StorageSize();
			CHECK_EQ(SerializedSize.MemorySize, 0);
			CHECK_EQ(SerializedSize.DiskSize, CacheSize.DiskSize);

			for (size_t Bucket = 0; Bucket < 4; ++Bucket)
			{
				Zcs.DropBucket(fmt::format("test_bucket-{}", Bucket));
			}
			CHECK_EQ(0, Zcs.StorageSize().DiskSize);
		}
	}
}

TEST_CASE("z$.gc")
{
	using namespace testutils;

	SUBCASE("gather references does NOT add references for expired cache entries")
	{
		ScopedTemporaryDirectory TempDir;
		std::vector<IoHash>		 Cids{CreateKey(1), CreateKey(2), CreateKey(3)};

		const auto CollectAndFilter = [](CasGc&					 Gc,
										 GcClock::TimePoint		 Time,
										 GcClock::Duration		 MaxDuration,
										 std::span<const IoHash> Cids,
										 std::vector<IoHash>&	 OutKeep) {
			GcContext GcCtx(Time);
			GcCtx.MaxCacheDuration(MaxDuration);
			Gc.CollectGarbage(GcCtx);
			OutKeep.clear();
			GcCtx.FilterCids(Cids, [&OutKeep](const IoHash& Hash) { OutKeep.push_back(Hash); });
		};

		{
			CasGc		  Gc;
			ZenCacheStore Zcs(Gc, TempDir.Path() / "cache");
			const auto	  Bucket = "teardrinker"sv;

			// Create a cache record
			const IoHash   Key = CreateKey(42);
			CbObjectWriter Record;
			Record << "Key"sv
				   << "SomeRecord"sv;

			for (size_t Idx = 0; auto& Cid : Cids)
			{
				Record.AddBinaryAttachment(fmt::format("attachment-{}", Idx++), Cid);
			}

			IoBuffer Buffer = Record.Save().GetBuffer().AsIoBuffer();
			Buffer.SetContentType(ZenContentType::kCbObject);

			Zcs.Put(Bucket, Key, {.Value = Buffer});

			std::vector<IoHash> Keep;

			// Collect garbage with 1 hour max cache duration
			{
				CollectAndFilter(Gc, GcClock::Now(), std::chrono::hours(1), Cids, Keep);
				CHECK_EQ(Cids.size(), Keep.size());
			}

			// Move forward in time
			{
				CollectAndFilter(Gc, GcClock::Now() + std::chrono::hours(2), std::chrono::hours(1), Cids, Keep);
				CHECK_EQ(0, Keep.size());
			}
		}

		// Expect timestamps to be serialized
		{
			CasGc				Gc;
			ZenCacheStore		Zcs(Gc, TempDir.Path() / "cache");
			std::vector<IoHash> Keep;

			// Collect garbage with 1 hour max cache duration
			{
				CollectAndFilter(Gc, GcClock::Now(), std::chrono::hours(1), Cids, Keep);
				CHECK_EQ(3, Keep.size());
			}

			// Move forward in time
			{
				CollectAndFilter(Gc, GcClock::Now() + std::chrono::hours(2), std::chrono::hours(1), Cids, Keep);
				CHECK_EQ(0, Keep.size());
			}
		}
	}

	SUBCASE("gc removes standalone values")
	{
		ScopedTemporaryDirectory TempDir;
		CasGc					 Gc;
		ZenCacheStore			 Zcs(Gc, TempDir.Path() / "cache");
		const auto				 Bucket		 = "fortysixandtwo"sv;
		const GcClock::TimePoint CurrentTime = GcClock::Now();

		std::vector<IoHash> Keys{CreateKey(1), CreateKey(2), CreateKey(3)};

		for (const auto& Key : Keys)
		{
			IoBuffer Value = testutils::CreateBinaryCacheValue(128 << 10);
			Zcs.Put(Bucket, Key, {.Value = Value});
		}

		{
			GcContext GcCtx;
			GcCtx.MaxCacheDuration(std::chrono::hours(46));

			Gc.CollectGarbage(GcCtx);

			for (const auto& Key : Keys)
			{
				ZenCacheValue CacheValue;
				const bool	  Exists = Zcs.Get(Bucket, Key, CacheValue);
				CHECK(Exists);
			}
		}

		// Move forward in time and collect again
		{
			GcContext GcCtx(CurrentTime + std::chrono::hours(46));
			GcCtx.MaxCacheDuration(std::chrono::minutes(2));

			Gc.CollectGarbage(GcCtx);

			for (const auto& Key : Keys)
			{
				ZenCacheValue CacheValue;
				const bool	  Exists = Zcs.Get(Bucket, Key, CacheValue);
				CHECK(!Exists);
			}

			CHECK_EQ(0, Zcs.StorageSize().DiskSize);
		}
	}

	SUBCASE("gc removes small objects")
	{
		ScopedTemporaryDirectory TempDir;
		CasGc					 Gc;
		ZenCacheStore			 Zcs(Gc, TempDir.Path() / "cache");
		const auto				 Bucket		 = "rightintwo"sv;
		const GcClock::TimePoint CurrentTime = GcClock::Now();

		std::vector<IoHash> Keys{CreateKey(1), CreateKey(2), CreateKey(3)};

		for (const auto& Key : Keys)
		{
			IoBuffer Value = testutils::CreateBinaryCacheValue(128);
			Zcs.Put(Bucket, Key, {.Value = Value});
		}

		{
			GcContext GcCtx;
			GcCtx.MaxCacheDuration(std::chrono::hours(2));
			GcCtx.CollectSmallObjects(true);

			Gc.CollectGarbage(GcCtx);

			for (const auto& Key : Keys)
			{
				ZenCacheValue CacheValue;
				const bool	  Exists = Zcs.Get(Bucket, Key, CacheValue);
				CHECK(Exists);
			}
		}

		// Move forward in time and collect again
		{
			GcContext GcCtx(CurrentTime + std::chrono::hours(2));
			GcCtx.MaxCacheDuration(std::chrono::minutes(2));
			GcCtx.CollectSmallObjects(true);

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

			for (const auto& Key : Keys)
			{
				ZenCacheValue CacheValue;
				const bool	  Exists = Zcs.Get(Bucket, Key, CacheValue);
				CHECK(!Exists);
			}

			CHECK_EQ(0, Zcs.StorageSize().DiskSize);
		}
	}
}

TEST_CASE("z$.legacyconversion")
{
	ScopedTemporaryDirectory TempDir;

	uint64_t			  ChunkSizes[]	  = {2041,
							 1123,
							 1223,
							 1239,
							 341,
							 1412,
							 912,
							 774,
							 341,
							 431,
							 554,
							 1098,
							 2048,
							 339 + 64 * 1024,
							 561 + 64 * 1024,
							 16 + 64 * 1024,
							 16 + 64 * 1024,
							 2048,
							 2048};
	size_t				  ChunkCount	  = sizeof(ChunkSizes) / sizeof(uint64_t);
	size_t				  SingleBlockSize = 0;
	std::vector<IoBuffer> Chunks;
	Chunks.reserve(ChunkCount);
	for (uint64_t Size : ChunkSizes)
	{
		Chunks.push_back(testutils::CreateBinaryCacheValue(Size));
		SingleBlockSize += Size;
	}

	std::vector<IoHash> ChunkHashes;
	ChunkHashes.reserve(ChunkCount);
	for (const IoBuffer& Chunk : Chunks)
	{
		ChunkHashes.push_back(IoHash::HashBuffer(Chunk.Data(), Chunk.Size()));
	}

	CreateDirectories(TempDir.Path());

	const std::string Bucket = "rightintwo";
	{
		CasGc					 Gc;
		ZenCacheStore			 Zcs(Gc, TempDir.Path());
		const GcClock::TimePoint CurrentTime = GcClock::Now();

		for (size_t i = 0; i < ChunkCount; i++)
		{
			Zcs.Put(Bucket, ChunkHashes[i], {.Value = Chunks[i]});
		}

		std::vector<IoHash> KeepChunks;
		for (size_t i = 0; i < ChunkCount; i += 2)
		{
			KeepChunks.push_back(ChunkHashes[i]);
		}
		GcContext GcCtx(CurrentTime + std::chrono::hours(2));
		GcCtx.MaxCacheDuration(std::chrono::minutes(2));
		GcCtx.CollectSmallObjects(true);
		GcCtx.ContributeCas(KeepChunks);
		Zcs.Flush();
		Gc.CollectGarbage(GcCtx);
	}
	std::filesystem::path BucketDir		= TempDir.Path() / Bucket;
	std::filesystem::path BlocksBaseDir = BucketDir / "blocks";

	std::filesystem::path CasPath		 = GetBlockPath(BlocksBaseDir, 1);
	std::filesystem::path LegacyDataPath = GetLegacyDataPath(BucketDir);
	std::filesystem::remove(LegacyDataPath);
	std::filesystem::rename(CasPath, LegacyDataPath);

	std::vector<DiskIndexEntry> LogEntries;
	std::filesystem::path		IndexPath = GetIndexPath(BucketDir, Bucket);
	if (std::filesystem::is_regular_file(IndexPath))
	{
		BasicFile ObjectIndexFile;
		ObjectIndexFile.Open(IndexPath, BasicFile::Mode::kRead);
		uint64_t Size = ObjectIndexFile.FileSize();
		if (Size >= sizeof(CacheBucketIndexHeader))
		{
			uint64_t			   ExpectedEntryCount = (Size - sizeof(sizeof(CacheBucketIndexHeader))) / sizeof(DiskIndexEntry);
			CacheBucketIndexHeader Header;
			ObjectIndexFile.Read(&Header, sizeof(Header), 0);
			if (Header.Magic == CacheBucketIndexHeader::ExpectedMagic && Header.Version == CacheBucketIndexHeader::CurrentVersion &&
				Header.PayloadAlignment > 0 && Header.EntryCount == ExpectedEntryCount)
			{
				LogEntries.resize(Header.EntryCount);
				ObjectIndexFile.Read(LogEntries.data(), Header.EntryCount * sizeof(DiskIndexEntry), sizeof(CacheBucketIndexHeader));
			}
		}
		ObjectIndexFile.Close();
		std::filesystem::remove(IndexPath);
	}

	std::filesystem::path LogPath = GetLogPath(BucketDir, Bucket);
	{
		TCasLogFile<DiskIndexEntry> CasLog;
		CasLog.Open(LogPath, CasLogFile::Mode::kRead);
		LogEntries.reserve(CasLog.GetLogCount());
		CasLog.Replay([&](const DiskIndexEntry& Record) { LogEntries.push_back(Record); }, 0);
	}
	TCasLogFile<LegacyDiskIndexEntry> LegacyLog;
	std::filesystem::path			  LegacylogPath = GetLegacyLogPath(BucketDir);
	LegacyLog.Open(LegacylogPath, CasLogFile::Mode::kTruncate);

	for (const DiskIndexEntry& Entry : LogEntries)
	{
		uint64_t Size;
		uint64_t Offset;
		if (Entry.Location.IsFlagSet(DiskLocation::kStandaloneFile))
		{
			Size   = Entry.Location.Location.StandaloneSize;
			Offset = 0;
		}
		else
		{
			BlockStoreLocation Location = Entry.Location.GetBlockLocation(16);
			Size						= Location.Size;
			Offset						= Location.Offset;
		}
		LegacyDiskLocation	 LegacyLocation(Offset, Size, 0, static_cast<uint64_t>(Entry.Location.Flags) << 56);
		LegacyDiskIndexEntry LegacyEntry = {.Key = Entry.Key, .Location = LegacyLocation};
		LegacyLog.Append(LegacyEntry);
	}
	LegacyLog.Close();

	std::filesystem::remove_all(BlocksBaseDir);
	std::filesystem::remove(LogPath);
	std::filesystem::remove(IndexPath);

	{
		CasGc		  Gc;
		ZenCacheStore Zcs(Gc, TempDir.Path());

		for (size_t i = 0; i < ChunkCount; i += 2)
		{
			ZenCacheValue Value;
			CHECK(Zcs.Get(Bucket, ChunkHashes[i], Value));
			CHECK(ChunkHashes[i] == IoHash::HashBuffer(Value.Value));
			CHECK(!Zcs.Get(Bucket, ChunkHashes[i + 1], Value));
		}
	}
}

TEST_CASE("z$.threadedinsert")	// * doctest::skip(true))
{
	//	for (uint32_t i = 0; i < 100; ++i)
	{
		ScopedTemporaryDirectory TempDir;

		const uint64_t kChunkSize  = 1048;
		const int32_t  kChunkCount = 8192;

		struct Chunk
		{
			std::string Bucket;
			IoBuffer	Buffer;
		};
		std::unordered_map<IoHash, Chunk, IoHash::Hasher> Chunks;
		Chunks.reserve(kChunkCount);

		const std::string Bucket1 = "rightinone";
		const std::string Bucket2 = "rightintwo";

		for (int32_t Idx = 0; Idx < kChunkCount; ++Idx)
		{
			while (true)
			{
				IoBuffer Chunk = testutils::CreateBinaryCacheValue(kChunkSize);
				IoHash	 Hash  = HashBuffer(Chunk);
				if (Chunks.contains(Hash))
				{
					continue;
				}
				Chunks[Hash] = {.Bucket = Bucket1, .Buffer = Chunk};
				break;
			}
			while (true)
			{
				IoBuffer Chunk = testutils::CreateBinaryCacheValue(kChunkSize);
				IoHash	 Hash  = HashBuffer(Chunk);
				if (Chunks.contains(Hash))
				{
					continue;
				}
				Chunks[Hash] = {.Bucket = Bucket2, .Buffer = Chunk};
				break;
			}
		}

		CreateDirectories(TempDir.Path());

		WorkerThreadPool ThreadPool(4);
		CasGc			 Gc;
		ZenCacheStore	 Zcs(Gc, TempDir.Path());

		{
			std::atomic<size_t> WorkCompleted = 0;
			for (const auto& Chunk : Chunks)
			{
				ThreadPool.ScheduleWork([&Zcs, &WorkCompleted, &Chunk]() {
					Zcs.Put(Chunk.second.Bucket, Chunk.first, {.Value = Chunk.second.Buffer});
					WorkCompleted.fetch_add(1);
				});
			}
			while (WorkCompleted < Chunks.size())
			{
				Sleep(1);
			}
		}

		const uint64_t TotalSize = Zcs.StorageSize().DiskSize;
		CHECK_EQ(kChunkSize * Chunks.size(), TotalSize);

		{
			std::atomic<size_t> WorkCompleted = 0;
			for (const auto& Chunk : Chunks)
			{
				ThreadPool.ScheduleWork([&Zcs, &WorkCompleted, &Chunk]() {
					std::string	  Bucket	= Chunk.second.Bucket;
					IoHash		  ChunkHash = Chunk.first;
					ZenCacheValue CacheValue;

					CHECK(Zcs.Get(Bucket, ChunkHash, CacheValue));
					IoHash Hash = IoHash::HashBuffer(CacheValue.Value);
					CHECK(ChunkHash == Hash);
					WorkCompleted.fetch_add(1);
				});
			}
			while (WorkCompleted < Chunks.size())
			{
				Sleep(1);
			}
		}
		std::unordered_map<IoHash, std::string, IoHash::Hasher> GcChunkHashes;
		GcChunkHashes.reserve(Chunks.size());
		for (const auto& Chunk : Chunks)
		{
			GcChunkHashes[Chunk.first] = Chunk.second.Bucket;
		}
		{
			std::unordered_map<IoHash, Chunk, IoHash::Hasher> NewChunks;

			for (int32_t Idx = 0; Idx < kChunkCount; ++Idx)
			{
				{
					IoBuffer Chunk	= testutils::CreateBinaryCacheValue(kChunkSize);
					IoHash	 Hash	= HashBuffer(Chunk);
					NewChunks[Hash] = {.Bucket = Bucket1, .Buffer = Chunk};
				}
				{
					IoBuffer Chunk	= testutils::CreateBinaryCacheValue(kChunkSize);
					IoHash	 Hash	= HashBuffer(Chunk);
					NewChunks[Hash] = {.Bucket = Bucket2, .Buffer = Chunk};
				}
			}

			std::atomic<size_t>	 WorkCompleted	 = 0;
			std::atomic_uint32_t AddedChunkCount = 0;
			for (const auto& Chunk : NewChunks)
			{
				ThreadPool.ScheduleWork([&Zcs, &WorkCompleted, Chunk, &AddedChunkCount]() {
					Zcs.Put(Chunk.second.Bucket, Chunk.first, {.Value = Chunk.second.Buffer});
					AddedChunkCount.fetch_add(1);
					WorkCompleted.fetch_add(1);
				});
			}

			for (const auto& Chunk : Chunks)
			{
				ThreadPool.ScheduleWork([&Zcs, &WorkCompleted, Chunk]() {
					ZenCacheValue CacheValue;
					if (Zcs.Get(Chunk.second.Bucket, Chunk.first, CacheValue))
					{
						CHECK(Chunk.first == IoHash::HashBuffer(CacheValue.Value));
					}
					WorkCompleted.fetch_add(1);
				});
			}
			while (AddedChunkCount.load() < NewChunks.size())
			{
				// Need to be careful since we might GC blocks we don't know outside of RwLock::ExclusiveLockScope
				for (const auto& Chunk : NewChunks)
				{
					ZenCacheValue CacheValue;
					if (Zcs.Get(Chunk.second.Bucket, Chunk.first, CacheValue))
					{
						GcChunkHashes[Chunk.first] = Chunk.second.Bucket;
					}
				}
				std::vector<IoHash> KeepHashes;
				KeepHashes.reserve(GcChunkHashes.size());
				for (const auto& Entry : GcChunkHashes)
				{
					KeepHashes.push_back(Entry.first);
				}
				size_t C = 0;
				while (C < KeepHashes.size())
				{
					if (C % 155 == 0)
					{
						if (C < KeepHashes.size() - 1)
						{
							KeepHashes[C] = KeepHashes[KeepHashes.size() - 1];
							KeepHashes.pop_back();
						}
						if (C + 3 < KeepHashes.size() - 1)
						{
							KeepHashes[C + 3] = KeepHashes[KeepHashes.size() - 1];
							KeepHashes.pop_back();
						}
					}
					C++;
				}

				GcContext GcCtx;
				GcCtx.CollectSmallObjects(true);
				GcCtx.ContributeCas(KeepHashes);
				Zcs.CollectGarbage(GcCtx);
				CasChunkSet& Deleted = GcCtx.DeletedCas();
				Deleted.IterateChunks([&GcChunkHashes](const IoHash& ChunkHash) { GcChunkHashes.erase(ChunkHash); });
			}

			while (WorkCompleted < NewChunks.size() + Chunks.size())
			{
				Sleep(1);
			}

			{
				// Need to be careful since we might GC blocks we don't know outside of RwLock::ExclusiveLockScope
				for (const auto& Chunk : NewChunks)
				{
					ZenCacheValue CacheValue;
					if (Zcs.Get(Chunk.second.Bucket, Chunk.first, CacheValue))
					{
						GcChunkHashes[Chunk.first] = Chunk.second.Bucket;
					}
				}
				std::vector<IoHash> KeepHashes;
				KeepHashes.reserve(GcChunkHashes.size());
				for (const auto& Entry : GcChunkHashes)
				{
					KeepHashes.push_back(Entry.first);
				}
				size_t C = 0;
				while (C < KeepHashes.size())
				{
					if (C % 155 == 0)
					{
						if (C < KeepHashes.size() - 1)
						{
							KeepHashes[C] = KeepHashes[KeepHashes.size() - 1];
							KeepHashes.pop_back();
						}
						if (C + 3 < KeepHashes.size() - 1)
						{
							KeepHashes[C + 3] = KeepHashes[KeepHashes.size() - 1];
							KeepHashes.pop_back();
						}
					}
					C++;
				}

				GcContext GcCtx;
				GcCtx.CollectSmallObjects(true);
				GcCtx.ContributeCas(KeepHashes);
				Zcs.CollectGarbage(GcCtx);
				CasChunkSet& Deleted = GcCtx.DeletedCas();
				Deleted.IterateChunks([&GcChunkHashes](const IoHash& ChunkHash) { GcChunkHashes.erase(ChunkHash); });
			}
		}
		{
			std::atomic<size_t> WorkCompleted = 0;
			for (const auto& Chunk : GcChunkHashes)
			{
				ThreadPool.ScheduleWork([&Zcs, &WorkCompleted, Chunk]() {
					ZenCacheValue CacheValue;
					CHECK(Zcs.Get(Chunk.second, Chunk.first, CacheValue));
					CHECK(Chunk.first == IoHash::HashBuffer(CacheValue.Value));
					WorkCompleted.fetch_add(1);
				});
			}
			while (WorkCompleted < GcChunkHashes.size())
			{
				Sleep(1);
			}
		}
	}
}

#endif

void
z$_forcelink()
{
}

}  // namespace zen