Size based gc trigger (#197)

- Feature: Disk size triggered GC, a soft disk usage limit for cache data.
- Feature: New option `--gc-disk-size-soft-limit` (command line), `gc.cache.disksizesoftlimit` (lua config) controlling limit for soft disk usage limit. Defaults to zero which disables soft disk usage limit.
- Improvement: Disk write pressure in GC log and cleaned up clutter in GC logging.

1 files changed, 465 insertions, 90 deletions

diff --git a/zenstore/gc.cpp b/zenstore/gc.cpp
index 8aac65bb4..4094716ae 100644
--- a/zenstore/gc.cpp
+++ b/zenstore/gc.cpp
@@ -36,6 +36,19 @@
 #	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;
@@ -176,17 +189,16 @@ struct GcContext::GcState
 	CacheKeyContexts   m_ExpiredCacheKeys;
 	HashKeySet		   m_RetainedCids;
 	HashKeySet		   m_DeletedCids;
-	GcClock::TimePoint m_GcTime;
-	GcClock::Duration  m_MaxCacheDuration	 = std::chrono::hours(24);
+	GcClock::TimePoint m_ExpireTime;
 	bool			   m_DeletionMode		 = true;
 	bool			   m_CollectSmallObjects = false;
 
 	std::filesystem::path DiskReservePath;
 };
 
-GcContext::GcContext(GcClock::TimePoint Time) : m_State(std::make_unique<GcState>())
+GcContext::GcContext(const GcClock::TimePoint& ExpireTime) : m_State(std::make_unique<GcState>())
 {
-	m_State->m_GcTime = Time;
+	m_State->m_ExpireTime = ExpireTime;
 }
 
 GcContext::~GcContext()
@@ -266,21 +278,9 @@ GcContext::CollectSmallObjects(bool NewState)
 }
 
 GcClock::TimePoint
-GcContext::Time() const
-{
-	return m_State->m_GcTime;
-}
-
-GcClock::Duration
-GcContext::MaxCacheDuration() const
-{
-	return m_State->m_MaxCacheDuration;
-}
-
-void
-GcContext::MaxCacheDuration(GcClock::Duration Duration)
+GcContext::ExpireTime() const
 {
-	m_State->m_MaxCacheDuration = Duration;
+	return m_State->m_ExpireTime;
 }
 
 void
@@ -330,7 +330,7 @@ GcStorage::~GcStorage()
 
 //////////////////////////////////////////////////////////////////////////
 
-GcManager::GcManager()
+GcManager::GcManager() : m_Log(logging::Get("gc"))
 {
 }
 
@@ -383,13 +383,22 @@ GcManager::CollectGarbage(GcContext& GcCtx)
 	}
 
 	// Then trim storage
-
 	{
-		Stopwatch  Timer;
-		const auto Guard = MakeGuard([&] { ZEN_INFO("collected garbage in {}", NiceTimeSpanMs(Timer.GetElapsedTimeMs())); });
+		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;
 		}
 	}
 }
@@ -432,6 +441,121 @@ GcManager::OnDroppedCidReferences(std::span<IoHash> Hashes)
 #endif
 
 //////////////////////////////////////////////////////////////////////////
+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)
 {
@@ -465,12 +589,14 @@ GcScheduler::Initialize(const GcSchedulerConfig& Config)
 				 Ec.message());
 	}
 
-	m_LastGcTime = GcClock::Now();
+	m_LastGcTime	   = GcClock::Now();
+	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?
@@ -478,6 +604,18 @@ GcScheduler::Initialize(const GcSchedulerConfig& Config)
 		}
 	}
 
+	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_NextGcTime = NextGcTime(m_LastGcTime);
 	m_GcThread	 = std::thread(&GcScheduler::SchedulerThread, this);
 }
@@ -500,6 +638,8 @@ GcScheduler::Shutdown()
 			m_GcThread.join();
 		}
 	}
+	m_DiskUsageLog.Flush();
+	m_DiskUsageLog.Close();
 }
 
 bool
@@ -547,34 +687,107 @@ GcScheduler::SchedulerThread()
 			continue;
 		}
 
+		bool				 Delete				 = true;
+		bool				 CollectSmallObjects = m_Config.CollectSmallObjects;
+		std::chrono::seconds MaxCacheDuration	 = m_Config.MaxCacheDuration;
+		uint64_t			 DiskSizeSoftLimit	 = m_Config.DiskSizeSoftLimit;
+		GcClock::TimePoint	 Now				 = GcClock::Now();
+		if (m_TriggerParams)
+		{
+			const auto TriggerParams = m_TriggerParams.value();
+			m_TriggerParams.reset();
+
+			CollectSmallObjects = TriggerParams.CollectSmallObjects;
+			if (TriggerParams.MaxCacheDuration != std::chrono::seconds::max())
+			{
+				MaxCacheDuration = TriggerParams.MaxCacheDuration;
+			}
+			if (TriggerParams.DiskSizeSoftLimit != 0)
+			{
+				DiskSizeSoftLimit = TriggerParams.DiskSizeSoftLimit;
+			}
+		}
+
+		GcClock::TimePoint ExpireTime = MaxCacheDuration == GcClock::Duration::max() ? GcClock::TimePoint::min() : Now - MaxCacheDuration;
+
+		std::error_code		Ec;
+		const GcStorageSize TotalSize = m_GcManager.TotalStorageSize();
+
 		if (Timeout && Status() == GcSchedulerStatus::kIdle)
 		{
-			std::error_code		 Ec;
-			DiskSpace			 Space		 = DiskSpaceInfo(m_Config.RootDirectory, Ec);
-			GcStorageSize		 TotalSize	 = m_GcManager.TotalStorageSize();
+			DiskSpace Space = DiskSpaceInfo(m_Config.RootDirectory, Ec);
+			if (Ec)
+			{
+				ZEN_WARN("get disk space info FAILED, reason: '{}'", Ec.message());
+			}
+
 			std::chrono::seconds RemaingTime = std::chrono::duration_cast<std::chrono::seconds>(m_NextGcTime - GcClock::Now());
 
+			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);
+				m_DiskUsageWindow.Append({.SampleTime = EpochTickCount, .DiskUsage = TotalSize.DiskSize});
+				m_DiskUsageLog.Append({.SampleTime = EpochTickCount, .DiskUsage = TotalSize.DiskSize});
+				const GcClock::TimePoint LoadGraphStartTime = Now - LoadGraphTime;
+				GcClock::Tick			 Start				= LoadGraphStartTime.time_since_epoch().count();
+				GcClock::Tick			 End				= Now.time_since_epoch().count();
+				DiskDeltas									= m_DiskUsageWindow.GetDiskDeltas(Start,
+															  End,
+															  Max(1, (End - Start + PressureGraphLength - 1) / PressureGraphLength),
+															  MaxLoad);
+			}
+
 			if (RemaingTime < std::chrono::seconds::zero())
 			{
 				RemaingTime = std::chrono::seconds::zero();
 			}
 
-			if (Ec)
+			std::string LoadGraph;
+			LoadGraph.resize(DiskDeltas.size(), '0');
+			if (DiskDeltas.size() > 0 && MaxLoad > 0)
 			{
-				ZEN_WARN("get disk space info FAILED, reason: '{}'", Ec.message());
+				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 > ExpireTime)
+				{
+					ExpireTime = SizeBasedExpireTime;
+				}
 			}
 
-			ZEN_INFO("{} in use, {} of total {} free disk space, {}",
+			bool DiskSpaceGCTriggered = GcDiskSpaceGoal > 0;
+			bool TimeBasedGCTriggered = !DiskSpaceGCTriggered && RemaingTime.count() == 0;
+			ZEN_INFO("{} in use,{} {} of total {} free disk space, disk writes last {} per {} [{}], peak {}/s. {}",
 					 NiceBytes(TotalSize.DiskSize),
+					 DiskSizeSoftLimit == 0 ? "" : fmt::format(" {} soft limit,", NiceBytes(DiskSizeSoftLimit)),
 					 NiceBytes(Space.Free),
 					 NiceBytes(Space.Total),
-					 m_Config.Interval.count()
-						 ? fmt::format("{} until next GC", NiceTimeSpanMs(uint64_t(std::chrono::milliseconds(RemaingTime).count())))
-						 : std::string("no GC scheduled"));
-
-			// TODO: Trigger GC if max disk usage water mark is reached
-
-			if (RemaingTime.count() > 0)
+					 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())),
+					 DiskSpaceGCTriggered ? fmt::format("Disk use threshold triggered, trying to reclaim {}. ", NiceBytes(GcDiskSpaceGoal))
+					 : TimeBasedGCTriggered ? "GC schedule triggered."
+											: fmt::format("{} until next scheduled GC.",
+														  NiceTimeSpanMs(uint64_t(std::chrono::milliseconds(RemaingTime).count()))));
+
+			if (!DiskSpaceGCTriggered && !TimeBasedGCTriggered)
 			{
 				WaitTime = m_Config.MonitorInterval < RemaingTime ? m_Config.MonitorInterval : RemaingTime;
 				continue;
@@ -588,54 +801,7 @@ GcScheduler::SchedulerThread()
 			}
 		}
 
-		GcContext GcCtx;
-		GcCtx.SetDeletionMode(true);
-		GcCtx.CollectSmallObjects(m_Config.CollectSmallObjects);
-		GcCtx.MaxCacheDuration(m_Config.MaxCacheDuration);
-		GcCtx.DiskReservePath(m_Config.RootDirectory / "reserve.gc");
-
-		if (m_TriggerParams)
-		{
-			const auto TriggerParams = m_TriggerParams.value();
-			m_TriggerParams.reset();
-
-			GcCtx.CollectSmallObjects(TriggerParams.CollectSmallObjects);
-			if (TriggerParams.MaxCacheDuration != std::chrono::seconds::max())
-			{
-				GcCtx.MaxCacheDuration(TriggerParams.MaxCacheDuration);
-			}
-		}
-
-		ZEN_INFO("garbage collection STARTING, small objects gc {}, max cache duration {}",
-				 GcCtx.CollectSmallObjects() ? "ENABLED"sv : "DISABLED"sv,
-				 NiceTimeSpanMs(uint64_t(std::chrono::duration_cast<std::chrono::milliseconds>(GcCtx.MaxCacheDuration()).count())));
-		{
-			Stopwatch  Timer;
-			const auto __ = MakeGuard([&] { ZEN_INFO("garbage collection DONE after {}", NiceTimeSpanMs(Timer.GetElapsedTimeMs())); });
-
-			m_GcManager.CollectGarbage(GcCtx);
-
-			m_LastGcTime = GcClock::Now();
-			m_NextGcTime = NextGcTime(m_LastGcTime);
-			WaitTime	 = m_Config.MonitorInterval;
-
-			{
-				const fs::path Path = m_Config.RootDirectory / "gc_state";
-				ZEN_DEBUG("saving scheduler state to '{}'", Path);
-				CbObjectWriter SchedulderState;
-				SchedulderState << "LastGcTime"sv << static_cast<int64_t>(m_LastGcTime.time_since_epoch().count());
-				SaveCompactBinaryObject(Path, SchedulderState.Save());
-			}
-
-			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());
-			}
-		}
+		CollectGarbage(ExpireTime, Delete, CollectSmallObjects);
 
 		uint32_t RunningState = static_cast<uint32_t>(GcSchedulerStatus::kRunning);
 		if (!m_Status.compare_exchange_strong(RunningState, static_cast<uint32_t>(GcSchedulerStatus::kIdle)))
@@ -643,6 +809,8 @@ GcScheduler::SchedulerThread()
 			ZEN_ASSERT(m_Status == static_cast<uint32_t>(GcSchedulerStatus::kStopped));
 			break;
 		}
+
+		WaitTime = m_Config.MonitorInterval;
 	}
 }
 
@@ -659,6 +827,54 @@ GcScheduler::NextGcTime(GcClock::TimePoint CurrentTime)
 	}
 }
 
+void
+GcScheduler::CollectGarbage(const GcClock::TimePoint& ExpireTime, bool Delete, bool CollectSmallObjects)
+{
+	GcContext GcCtx(ExpireTime);
+	GcCtx.SetDeletionMode(Delete);
+	GcCtx.CollectSmallObjects(CollectSmallObjects);
+	//	GcCtx.MaxCacheDuration(MaxCacheDuration);
+	GcCtx.DiskReservePath(m_Config.RootDirectory / "reserve.gc");
+
+	ZEN_INFO("garbage collection STARTING, small objects gc {}, cutoff time {}",
+			 GcCtx.CollectSmallObjects() ? "ENABLED"sv : "DISABLED"sv,
+			 ExpireTime);
+	{
+		Stopwatch  Timer;
+		const auto __ = MakeGuard([&] { ZEN_INFO("garbage collection DONE in {}", NiceTimeSpanMs(Timer.GetElapsedTimeMs())); });
+
+		m_GcManager.CollectGarbage(GcCtx);
+
+		if (Delete)
+		{
+			m_LastGcExpireTime = ExpireTime;
+			std::unique_lock Lock(m_GcMutex);
+			m_DiskUsageWindow.KeepRange(ExpireTime.time_since_epoch().count(), GcClock::Duration::max().count());
+		}
+
+		m_LastGcTime = GcClock::Now();
+		m_NextGcTime = NextGcTime(m_LastGcTime);
+
+		{
+			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());
+		}
+
+		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());
+		}
+	}
+}
+
 //////////////////////////////////////////////////////////////////////////
 
 #if ZEN_WITH_TESTS
@@ -704,7 +920,7 @@ TEST_CASE("gc.basic")
 	const auto InsertResult = CidStore.AddChunk(CompressedChunk);
 	CHECK(InsertResult.New);
 
-	GcContext GcCtx;
+	GcContext GcCtx(GcClock::Now() - std::chrono::hours(24));
 	GcCtx.CollectSmallObjects(true);
 
 	CidStore.Flush();
@@ -761,7 +977,7 @@ TEST_CASE("gc.full")
 
 	// Keep first and last
 	{
-		GcContext GcCtx;
+		GcContext GcCtx(GcClock::Now() - std::chrono::hours(24));
 		GcCtx.CollectSmallObjects(true);
 
 		std::vector<IoHash> KeepChunks;
@@ -796,7 +1012,7 @@ TEST_CASE("gc.full")
 
 	// Keep last
 	{
-		GcContext GcCtx;
+		GcContext GcCtx(GcClock::Now() - std::chrono::hours(24));
 		GcCtx.CollectSmallObjects(true);
 		std::vector<IoHash> KeepChunks;
 		KeepChunks.push_back(ChunkHashes[8]);
@@ -828,7 +1044,7 @@ TEST_CASE("gc.full")
 
 	// Keep mixed
 	{
-		GcContext GcCtx;
+		GcContext GcCtx(GcClock::Now() - std::chrono::hours(24));
 		GcCtx.CollectSmallObjects(true);
 		std::vector<IoHash> KeepChunks;
 		KeepChunks.push_back(ChunkHashes[1]);
@@ -863,7 +1079,7 @@ TEST_CASE("gc.full")
 
 	// Keep multiple at end
 	{
-		GcContext GcCtx;
+		GcContext GcCtx(GcClock::Now() - std::chrono::hours(24));
 		GcCtx.CollectSmallObjects(true);
 		std::vector<IoHash> KeepChunks;
 		KeepChunks.push_back(ChunkHashes[6]);
@@ -912,6 +1128,165 @@ TEST_CASE("gc.full")
 	CHECK_LE(InitialSize.TinySize, FinalSize.TinySize);
 	CHECK_GE(InitialSize.TinySize + (1u << 28), FinalSize.TinySize);
 }
+
+TEST_CASE("gc.diskusagewindow")
+{
+	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));
+	}
+}
 #endif
 
 void