aboutsummaryrefslogtreecommitdiff
path: root/src/zenremotestore/chunking
diff options
context:
space:
mode:
Diffstat (limited to 'src/zenremotestore/chunking')
-rw-r--r--src/zenremotestore/chunking/chunkblock.cpp1749
-rw-r--r--src/zenremotestore/chunking/chunkedcontent.cpp8
-rw-r--r--src/zenremotestore/chunking/chunkedfile.cpp4
-rw-r--r--src/zenremotestore/chunking/chunkingcache.cpp12
4 files changed, 1269 insertions, 504 deletions
diff --git a/src/zenremotestore/chunking/chunkblock.cpp b/src/zenremotestore/chunking/chunkblock.cpp
index d203e0292..f29112f53 100644
--- a/src/zenremotestore/chunking/chunkblock.cpp
+++ b/src/zenremotestore/chunking/chunkblock.cpp
@@ -8,13 +8,9 @@
#include <zencore/timer.h>
#include <zencore/trace.h>
-#include <zenremotestore/operationlogoutput.h>
-
#include <numeric>
-#include <vector>
ZEN_THIRD_PARTY_INCLUDES_START
-#include <tsl/robin_map.h>
#include <tsl/robin_set.h>
ZEN_THIRD_PARTY_INCLUDES_END
@@ -27,6 +23,184 @@ namespace zen {
using namespace std::literals;
+namespace chunkblock_impl {
+
+ struct RangeDescriptor
+ {
+ uint64_t RangeStart = 0;
+ uint64_t RangeLength = 0;
+ uint32_t ChunkBlockIndexStart = 0;
+ uint32_t ChunkBlockIndexCount = 0;
+ };
+
+ void MergeCheapestRange(std::vector<RangeDescriptor>& InOutRanges)
+ {
+ ZEN_ASSERT(InOutRanges.size() > 1);
+
+ size_t BestRangeIndexToCollapse = SIZE_MAX;
+ uint64_t BestGap = (uint64_t)-1;
+
+ for (size_t RangeIndex = 0; RangeIndex < InOutRanges.size() - 1; RangeIndex++)
+ {
+ const RangeDescriptor& Range = InOutRanges[RangeIndex];
+ const RangeDescriptor& NextRange = InOutRanges[RangeIndex + 1];
+ uint64_t Gap = NextRange.RangeStart - (Range.RangeStart + Range.RangeLength);
+ if (Gap < BestGap)
+ {
+ BestRangeIndexToCollapse = RangeIndex;
+ BestGap = Gap;
+ }
+ else if (Gap == BestGap)
+ {
+ const RangeDescriptor& BestRange = InOutRanges[BestRangeIndexToCollapse];
+ const RangeDescriptor& BestNextRange = InOutRanges[BestRangeIndexToCollapse + 1];
+ uint64_t BestMergedSize = (BestNextRange.RangeStart + BestNextRange.RangeLength) - BestRange.RangeStart;
+ uint64_t MergedSize = (NextRange.RangeStart + NextRange.RangeLength) - Range.RangeStart;
+ if (MergedSize < BestMergedSize)
+ {
+ BestRangeIndexToCollapse = RangeIndex;
+ }
+ }
+ }
+
+ ZEN_ASSERT(BestRangeIndexToCollapse != SIZE_MAX);
+ ZEN_ASSERT(BestRangeIndexToCollapse < InOutRanges.size() - 1);
+ ZEN_ASSERT(BestGap != (uint64_t)-1);
+
+ RangeDescriptor& BestRange = InOutRanges[BestRangeIndexToCollapse];
+ const RangeDescriptor& BestNextRange = InOutRanges[BestRangeIndexToCollapse + 1];
+ BestRange.RangeLength = BestNextRange.RangeStart - BestRange.RangeStart + BestNextRange.RangeLength;
+ BestRange.ChunkBlockIndexCount =
+ BestNextRange.ChunkBlockIndexStart - BestRange.ChunkBlockIndexStart + BestNextRange.ChunkBlockIndexCount;
+ InOutRanges.erase(InOutRanges.begin() + BestRangeIndexToCollapse + 1);
+ }
+
+ std::vector<RangeDescriptor> GetBlockRanges(const ChunkBlockDescription& BlockDescription,
+ const uint64_t ChunkStartOffsetInBlock,
+ std::span<const uint32_t> BlockChunkIndexNeeded)
+ {
+ ZEN_TRACE_CPU("GetBlockRanges");
+ std::vector<RangeDescriptor> BlockRanges;
+ {
+ uint64_t CurrentOffset = ChunkStartOffsetInBlock;
+ uint32_t ChunkBlockIndex = 0;
+ uint32_t NeedBlockChunkIndexOffset = 0;
+ RangeDescriptor NextRange;
+ while (NeedBlockChunkIndexOffset < BlockChunkIndexNeeded.size() && ChunkBlockIndex < BlockDescription.ChunkRawHashes.size())
+ {
+ const uint32_t ChunkCompressedLength = BlockDescription.ChunkCompressedLengths[ChunkBlockIndex];
+ if (ChunkBlockIndex < BlockChunkIndexNeeded[NeedBlockChunkIndexOffset])
+ {
+ if (NextRange.RangeLength > 0)
+ {
+ BlockRanges.push_back(NextRange);
+ NextRange = {};
+ }
+ ChunkBlockIndex++;
+ CurrentOffset += ChunkCompressedLength;
+ }
+ else if (ChunkBlockIndex == BlockChunkIndexNeeded[NeedBlockChunkIndexOffset])
+ {
+ if (NextRange.RangeLength == 0)
+ {
+ NextRange.RangeStart = CurrentOffset;
+ NextRange.ChunkBlockIndexStart = ChunkBlockIndex;
+ }
+ NextRange.RangeLength += ChunkCompressedLength;
+ NextRange.ChunkBlockIndexCount++;
+ ChunkBlockIndex++;
+ CurrentOffset += ChunkCompressedLength;
+ NeedBlockChunkIndexOffset++;
+ }
+ else
+ {
+ ZEN_ASSERT(false);
+ }
+ }
+ if (NextRange.RangeLength > 0)
+ {
+ BlockRanges.push_back(NextRange);
+ }
+ }
+ ZEN_ASSERT(!BlockRanges.empty());
+ return BlockRanges;
+ }
+
+ std::vector<RangeDescriptor> OptimizeRanges(uint64_t TotalBlockSize,
+ std::span<const RangeDescriptor> ExactRanges,
+ double LatencySec,
+ uint64_t SpeedBytesPerSec,
+ uint64_t MaxRangeCountPerRequest,
+ uint64_t MaxRangesPerBlock)
+ {
+ ZEN_TRACE_CPU("OptimizeRanges");
+ ZEN_ASSERT(MaxRangesPerBlock > 0);
+ std::vector<RangeDescriptor> Ranges(ExactRanges.begin(), ExactRanges.end());
+
+ while (Ranges.size() > MaxRangesPerBlock)
+ {
+ MergeCheapestRange(Ranges);
+ }
+
+ while (true)
+ {
+ const std::uint64_t RangeTotalSize =
+ std::accumulate(Ranges.begin(), Ranges.end(), uint64_t(0u), [](uint64_t Current, const RangeDescriptor& Value) {
+ return Current + Value.RangeLength;
+ });
+
+ const size_t RangeCount = Ranges.size();
+ const uint64_t RequestCount =
+ MaxRangeCountPerRequest == (uint64_t)-1 ? 1 : (RangeCount + MaxRangeCountPerRequest - 1) / MaxRangeCountPerRequest;
+ uint64_t RequestTimeAsBytes = uint64_t(SpeedBytesPerSec * RequestCount * LatencySec);
+
+ if (RangeCount == 1)
+ {
+ // Does fetching the full block add less time than the time it takes to complete a single request?
+ if (TotalBlockSize - RangeTotalSize < SpeedBytesPerSec * LatencySec)
+ {
+ const std::uint64_t InitialRangeTotalSize =
+ std::accumulate(ExactRanges.begin(),
+ ExactRanges.end(),
+ uint64_t(0u),
+ [](uint64_t Current, const RangeDescriptor& Value) { return Current + Value.RangeLength; });
+
+ ZEN_DEBUG(
+ "Latency round trip takes as long as receiving the extra redundant bytes - go full block, dropping {} of slack, "
+ "adding {} of bytes to fetch, for block of size {}",
+ NiceBytes(TotalBlockSize - RangeTotalSize),
+ NiceBytes(TotalBlockSize - InitialRangeTotalSize),
+ NiceBytes(TotalBlockSize));
+ return {};
+ }
+ else
+ {
+ return Ranges;
+ }
+ }
+
+ if (RequestTimeAsBytes < (TotalBlockSize - RangeTotalSize))
+ {
+ return Ranges;
+ }
+
+ if (RangeCount == 2)
+ {
+ // Merge to single range
+ Ranges.front().RangeLength = Ranges.back().RangeStart - Ranges.front().RangeStart + Ranges.back().RangeLength;
+ Ranges.front().ChunkBlockIndexCount =
+ Ranges.back().ChunkBlockIndexStart - Ranges.front().ChunkBlockIndexStart + Ranges.back().ChunkBlockIndexCount;
+ Ranges.pop_back();
+ }
+ else
+ {
+ MergeCheapestRange(Ranges);
+ }
+ }
+ }
+
+} // namespace chunkblock_impl
+
ChunkBlockDescription
ParseChunkBlockDescription(const CbObjectView& BlockObject)
{
@@ -177,9 +351,9 @@ GenerateChunkBlock(std::vector<std::pair<IoHash, FetchChunkFunc>>&& FetchChunks,
BufferEndPtr += WriteVarUInt(gsl::narrow<uint64_t>(ChunkCount), BufferEndPtr);
for (const auto& It : FetchChunks)
{
- std::pair<uint64_t, CompressedBuffer> Chunk = It.second(It.first);
- uint64_t ChunkSize = 0;
- std::span<const SharedBuffer> Segments = Chunk.second.GetCompressed().GetSegments();
+ std::pair<uint64_t, CompositeBuffer> Chunk = It.second(It.first);
+ uint64_t ChunkSize = 0;
+ std::span<const SharedBuffer> Segments = Chunk.second.GetSegments();
for (const SharedBuffer& Segment : Segments)
{
ZEN_ASSERT(Segment.IsOwned());
@@ -270,7 +444,7 @@ IterateChunkBlock(const SharedBuffer& BlockPayload,
};
std::vector<size_t>
-FindReuseBlocks(OperationLogOutput& Output,
+FindReuseBlocks(LoggerRef InLog,
const uint8_t BlockReuseMinPercentLimit,
const bool IsVerbose,
ReuseBlocksStatistics& Stats,
@@ -280,6 +454,7 @@ FindReuseBlocks(OperationLogOutput& Output,
std::vector<uint32_t>& OutUnusedChunkIndexes)
{
ZEN_TRACE_CPU("FindReuseBlocks");
+ ZEN_SCOPED_LOG(InLog);
// Find all blocks with a usage level higher than MinPercentLimit
// Pick out the blocks with usage higher or equal to MinPercentLimit
@@ -346,11 +521,10 @@ FindReuseBlocks(OperationLogOutput& Output,
{
if (IsVerbose)
{
- ZEN_OPERATION_LOG_INFO(Output,
- "Reusing block {}. {} attachments found, usage level: {}%",
- KnownBlock.BlockHash,
- FoundAttachmentCount,
- ReusePercent);
+ ZEN_INFO("Reusing block {}. {} attachments found, usage level: {}%",
+ KnownBlock.BlockHash,
+ FoundAttachmentCount,
+ ReusePercent);
}
ReuseBlockIndexes.push_back(KnownBlockIndex);
@@ -359,12 +533,13 @@ FindReuseBlocks(OperationLogOutput& Output,
}
else if (FoundAttachmentCount > 0)
{
- // if (IsVerbose)
- //{
- // ZEN_OPERATION_LOG_INFO(Output, "Skipping block {}. {} attachments found, usage level: {}%",
- // KnownBlock.BlockHash,
- // FoundAttachmentCount, ReusePercent);
- //}
+ if (IsVerbose)
+ {
+ ZEN_INFO("Skipping block {}. {} attachments found, usage level: {}%",
+ KnownBlock.BlockHash,
+ FoundAttachmentCount,
+ ReusePercent);
+ }
Stats.RejectedBlockCount++;
Stats.RejectedChunkCount += FoundAttachmentCount;
Stats.RejectedByteCount += ReuseSize;
@@ -408,11 +583,10 @@ FindReuseBlocks(OperationLogOutput& Output,
{
if (IsVerbose)
{
- ZEN_OPERATION_LOG_INFO(Output,
- "Reusing block {}. {} attachments found, usage level: {}%",
- KnownBlock.BlockHash,
- FoundChunkIndexes.size(),
- ReusePercent);
+ ZEN_INFO("Reusing block {}. {} attachments found, usage level: {}%",
+ KnownBlock.BlockHash,
+ FoundChunkIndexes.size(),
+ ReusePercent);
}
FilteredReuseBlockIndexes.push_back(KnownBlockIndex);
@@ -429,11 +603,10 @@ FindReuseBlocks(OperationLogOutput& Output,
}
else
{
- // if (IsVerbose)
- //{
- // ZEN_OPERATION_LOG_INFO(Output, "Skipping block {}. filtered usage level: {}%", KnownBlock.BlockHash,
- // ReusePercent);
- //}
+ if (IsVerbose)
+ {
+ ZEN_INFO("Skipping block {}. filtered usage level: {}%", KnownBlock.BlockHash, ReusePercent);
+ }
Stats.RejectedBlockCount++;
Stats.RejectedChunkCount += FoundChunkIndexes.size();
Stats.RejectedByteCount += AdjustedReuseSize;
@@ -454,10 +627,8 @@ FindReuseBlocks(OperationLogOutput& Output,
return FilteredReuseBlockIndexes;
}
-ChunkBlockAnalyser::ChunkBlockAnalyser(OperationLogOutput& LogOutput,
- std::span<const ChunkBlockDescription> BlockDescriptions,
- const Options& Options)
-: m_LogOutput(LogOutput)
+ChunkBlockAnalyser::ChunkBlockAnalyser(LoggerRef Log, std::span<const ChunkBlockDescription> BlockDescriptions, const Options& Options)
+: m_Log(Log)
, m_BlockDescriptions(BlockDescriptions)
, m_Options(Options)
{
@@ -555,480 +726,198 @@ ChunkBlockAnalyser::CalculatePartialBlockDownloads(std::span<const NeededBlock>
ChunkBlockAnalyser::BlockResult Result;
- uint64_t IdealDownloadTotalSize = 0;
- uint64_t AllBlocksTotalBlocksSize = 0;
-
- for (const NeededBlock& NeededBlock : NeededBlocks)
{
- const ChunkBlockDescription& BlockDescription = m_BlockDescriptions[NeededBlock.BlockIndex];
-
- std::span<const uint32_t> BlockChunkIndexNeeded(NeededBlock.ChunkIndexes);
- if (!NeededBlock.ChunkIndexes.empty())
+ uint64_t MinRequestCount = 0;
+ uint64_t RequestCount = 0;
+ uint64_t RangeCount = 0;
+ uint64_t IdealDownloadTotalSize = 0;
+ uint64_t ActualDownloadTotalSize = 0;
+ uint64_t FullDownloadTotalSize = 0;
+ for (const NeededBlock& NeededBlock : NeededBlocks)
{
- bool WantsToDoPartialBlockDownload = NeededBlock.ChunkIndexes.size() < BlockDescription.ChunkRawHashes.size();
- bool CanDoPartialBlockDownload = (BlockDescription.HeaderSize > 0) &&
- (BlockDescription.ChunkCompressedLengths.size() == BlockDescription.ChunkRawHashes.size());
-
- EPartialBlockDownloadMode PartialBlockDownloadMode = BlockPartialDownloadModes[NeededBlock.BlockIndex];
-
- const uint32_t ChunkStartOffsetInBlock =
+ const ChunkBlockDescription& BlockDescription = m_BlockDescriptions[NeededBlock.BlockIndex];
+ std::span<const uint32_t> BlockChunkIndexNeeded(NeededBlock.ChunkIndexes);
+ const uint32_t ChunkStartOffsetInBlock =
gsl::narrow<uint32_t>(CompressedBuffer::GetHeaderSizeForNoneEncoder() + BlockDescription.HeaderSize);
+ uint64_t TotalBlockSize = std::accumulate(BlockDescription.ChunkCompressedLengths.begin(),
+ BlockDescription.ChunkCompressedLengths.end(),
+ uint64_t(ChunkStartOffsetInBlock));
+ uint64_t ExactRangesSize = 0;
+ uint64_t DownloadRangesSize = 0;
+ uint64_t FullDownloadSize = 0;
+
+ bool CanDoPartialBlockDownload = (BlockDescription.HeaderSize > 0) &&
+ (BlockDescription.ChunkCompressedLengths.size() == BlockDescription.ChunkRawHashes.size());
- const uint64_t TotalBlockSize = std::accumulate(BlockDescription.ChunkCompressedLengths.begin(),
- BlockDescription.ChunkCompressedLengths.end(),
- std::uint64_t(ChunkStartOffsetInBlock));
-
- AllBlocksTotalBlocksSize += TotalBlockSize;
-
- if ((PartialBlockDownloadMode != EPartialBlockDownloadMode::Off) && WantsToDoPartialBlockDownload && CanDoPartialBlockDownload)
+ if (NeededBlock.ChunkIndexes.size() == BlockDescription.ChunkRawHashes.size() || !CanDoPartialBlockDownload)
{
- ZEN_TRACE_CPU("PartialBlockAnalysis");
-
- uint64_t TotalWantedChunksSize = 0;
- std::optional<std::vector<BlockRangeDescriptor>> MaybeBlockRanges = CalculateBlockRanges(NeededBlock.BlockIndex,
- BlockDescription,
- NeededBlock.ChunkIndexes,
- PartialBlockDownloadMode,
- ChunkStartOffsetInBlock,
- TotalBlockSize,
- TotalWantedChunksSize);
- ZEN_ASSERT(TotalWantedChunksSize <= TotalBlockSize);
- IdealDownloadTotalSize += TotalWantedChunksSize;
-
- if (MaybeBlockRanges.has_value())
+ // Full block
+ ExactRangesSize = TotalBlockSize;
+ DownloadRangesSize = TotalBlockSize;
+ FullDownloadSize = TotalBlockSize;
+ MinRequestCount++;
+ RequestCount++;
+ RangeCount++;
+ Result.FullBlockIndexes.push_back(NeededBlock.BlockIndex);
+ }
+ else if (NeededBlock.ChunkIndexes.empty())
+ {
+ // Not needed
+ }
+ else
+ {
+ FullDownloadSize = TotalBlockSize;
+ std::vector<chunkblock_impl::RangeDescriptor> Ranges =
+ chunkblock_impl::GetBlockRanges(BlockDescription, ChunkStartOffsetInBlock, BlockChunkIndexNeeded);
+ ExactRangesSize = std::accumulate(
+ Ranges.begin(),
+ Ranges.end(),
+ uint64_t(0),
+ [](uint64_t Current, const chunkblock_impl::RangeDescriptor& Range) { return Current + Range.RangeLength; });
+
+ EPartialBlockDownloadMode PartialBlockDownloadMode = BlockPartialDownloadModes[NeededBlock.BlockIndex];
+ if (PartialBlockDownloadMode == EPartialBlockDownloadMode::Off)
{
- std::vector<BlockRangeDescriptor> BlockRanges = MaybeBlockRanges.value();
- ZEN_ASSERT(!BlockRanges.empty());
-
- uint64_t RequestedSize =
- std::accumulate(BlockRanges.begin(),
- BlockRanges.end(),
- uint64_t(0),
- [](uint64_t Current, const BlockRangeDescriptor& Range) { return Current + Range.RangeLength; });
+ // Use full block
+ MinRequestCount++;
+ RangeCount++;
+ RequestCount++;
+ Result.FullBlockIndexes.push_back(NeededBlock.BlockIndex);
+ DownloadRangesSize = TotalBlockSize;
+ }
+ else
+ {
+ const bool IsHighSpeed = (PartialBlockDownloadMode == EPartialBlockDownloadMode::MultiRangeHighSpeed);
+ uint64_t MaxRangeCountPerRequest =
+ IsHighSpeed ? m_Options.HostHighSpeedMaxRangeCountPerRequest : m_Options.HostMaxRangeCountPerRequest;
+ ZEN_ASSERT(MaxRangeCountPerRequest != 0);
- if (PartialBlockDownloadMode != EPartialBlockDownloadMode::Exact && BlockRanges.size() > 1)
+ if (PartialBlockDownloadMode == EPartialBlockDownloadMode::Exact)
{
- // TODO: Once we have support in our http client to request multiple ranges in one request this
- // logic would need to change as the per-request overhead would go away
-
- const double LatencySec = PartialBlockDownloadMode == EPartialBlockDownloadMode::MultiRangeHighSpeed
- ? m_Options.HostHighSpeedLatencySec
- : m_Options.HostLatencySec;
- if (LatencySec > 0)
+ // Use exact ranges
+ for (const chunkblock_impl::RangeDescriptor& Range : Ranges)
{
- const uint64_t BytesPerSec = PartialBlockDownloadMode == EPartialBlockDownloadMode::MultiRangeHighSpeed
- ? m_Options.HostHighSpeedBytesPerSec
- : m_Options.HostSpeedBytesPerSec;
-
- const double ExtraRequestTimeSec = (BlockRanges.size() - 1) * LatencySec;
- const uint64_t ExtraRequestTimeBytes = uint64_t(ExtraRequestTimeSec * BytesPerSec);
-
- const uint64_t FullRangeSize =
- BlockRanges.back().RangeStart + BlockRanges.back().RangeLength - BlockRanges.front().RangeStart;
+ Result.BlockRanges.push_back(BlockRangeDescriptor{.BlockIndex = NeededBlock.BlockIndex,
+ .RangeStart = Range.RangeStart,
+ .RangeLength = Range.RangeLength,
+ .ChunkBlockIndexStart = Range.ChunkBlockIndexStart,
+ .ChunkBlockIndexCount = Range.ChunkBlockIndexCount});
+ }
- if (ExtraRequestTimeBytes + RequestedSize >= FullRangeSize)
+ MinRequestCount++;
+ RangeCount += Ranges.size();
+ RequestCount += MaxRangeCountPerRequest == (uint64_t)-1
+ ? 1
+ : (Ranges.size() + MaxRangeCountPerRequest - 1) / MaxRangeCountPerRequest;
+ DownloadRangesSize = ExactRangesSize;
+ }
+ else
+ {
+ if (PartialBlockDownloadMode == EPartialBlockDownloadMode::SingleRange)
+ {
+ // Use single range
+ if (Ranges.size() > 1)
{
- BlockRanges = std::vector<BlockRangeDescriptor>{MergeBlockRanges(BlockRanges)};
-
- if (m_Options.IsVerbose)
- {
- ZEN_OPERATION_LOG_INFO(m_LogOutput,
- "Merging {} chunks ({}) from block {} ({}) to single request (extra bytes {})",
- NeededBlock.ChunkIndexes.size(),
- NiceBytes(RequestedSize),
- BlockDescription.BlockHash,
- NiceBytes(TotalBlockSize),
- NiceBytes(BlockRanges.front().RangeLength - RequestedSize));
- }
-
- RequestedSize = BlockRanges.front().RangeLength;
+ Ranges = {chunkblock_impl::RangeDescriptor{
+ .RangeStart = Ranges.front().RangeStart,
+ .RangeLength = Ranges.back().RangeStart + Ranges.back().RangeLength - Ranges.front().RangeStart,
+ .ChunkBlockIndexStart = Ranges.front().ChunkBlockIndexStart,
+ .ChunkBlockIndexCount = Ranges.back().ChunkBlockIndexStart + Ranges.back().ChunkBlockIndexCount -
+ Ranges.front().ChunkBlockIndexStart}};
}
+
+ // We still do the optimize pass to see if it is more effective to use a full block
}
- }
- if ((PartialBlockDownloadMode != EPartialBlockDownloadMode::Exact) &&
- ((TotalBlockSize - RequestedSize) < (512u * 1024u)))
- {
- if (m_Options.IsVerbose)
+ double LatencySec = IsHighSpeed ? m_Options.HostHighSpeedLatencySec : m_Options.HostLatencySec;
+ uint64_t SpeedBytesPerSec = IsHighSpeed ? m_Options.HostHighSpeedBytesPerSec : m_Options.HostSpeedBytesPerSec;
+ if (LatencySec > 0.0 && SpeedBytesPerSec > 0u)
{
- ZEN_OPERATION_LOG_INFO(m_LogOutput,
- "Requesting {} chunks ({}) from block {} ({}) using full block request due to small "
- "total slack (extra bytes {})",
- NeededBlock.ChunkIndexes.size(),
- NiceBytes(RequestedSize),
- BlockDescription.BlockHash,
- NiceBytes(TotalBlockSize),
- NiceBytes(TotalBlockSize - TotalWantedChunksSize));
+ Ranges = chunkblock_impl::OptimizeRanges(TotalBlockSize,
+ Ranges,
+ LatencySec,
+ SpeedBytesPerSec,
+ MaxRangeCountPerRequest,
+ m_Options.MaxRangesPerBlock);
}
- Result.FullBlockIndexes.push_back(NeededBlock.BlockIndex);
- }
- else
- {
- Result.BlockRanges.insert(Result.BlockRanges.end(), BlockRanges.begin(), BlockRanges.end());
- if (m_Options.IsVerbose)
+ MinRequestCount++;
+ if (Ranges.empty())
{
- ZEN_OPERATION_LOG_INFO(m_LogOutput,
- "Requesting {} chunks ({}) from block {} ({}) using {} requests (extra bytes {})",
- NeededBlock.ChunkIndexes.size(),
- NiceBytes(RequestedSize),
- BlockDescription.BlockHash,
- NiceBytes(TotalBlockSize),
- BlockRanges.size(),
- NiceBytes(RequestedSize - TotalWantedChunksSize));
+ Result.FullBlockIndexes.push_back(NeededBlock.BlockIndex);
+ RequestCount++;
+ RangeCount++;
+ DownloadRangesSize = TotalBlockSize;
}
+ else
+ {
+ for (const chunkblock_impl::RangeDescriptor& Range : Ranges)
+ {
+ Result.BlockRanges.push_back(BlockRangeDescriptor{.BlockIndex = NeededBlock.BlockIndex,
+ .RangeStart = Range.RangeStart,
+ .RangeLength = Range.RangeLength,
+ .ChunkBlockIndexStart = Range.ChunkBlockIndexStart,
+ .ChunkBlockIndexCount = Range.ChunkBlockIndexCount});
+ }
+ RangeCount += Ranges.size();
+ RequestCount += MaxRangeCountPerRequest == (uint64_t)-1
+ ? 1
+ : (Ranges.size() + MaxRangeCountPerRequest - 1) / MaxRangeCountPerRequest;
+ }
+
+ DownloadRangesSize = Ranges.empty()
+ ? TotalBlockSize
+ : std::accumulate(Ranges.begin(),
+ Ranges.end(),
+ uint64_t(0),
+ [](uint64_t Current, const chunkblock_impl::RangeDescriptor& Range) {
+ return Current + Range.RangeLength;
+ });
}
}
- else
- {
- Result.FullBlockIndexes.push_back(NeededBlock.BlockIndex);
- }
}
- else
- {
- Result.FullBlockIndexes.push_back(NeededBlock.BlockIndex);
- IdealDownloadTotalSize += TotalBlockSize;
- }
- }
- }
+ IdealDownloadTotalSize += ExactRangesSize;
+ ActualDownloadTotalSize += DownloadRangesSize;
+ FullDownloadTotalSize += FullDownloadSize;
- if (!Result.BlockRanges.empty() && !m_Options.IsQuiet)
- {
- tsl::robin_set<uint32_t> PartialBlockIndexes;
- uint64_t PartialBlocksTotalSize = std::accumulate(Result.BlockRanges.begin(),
- Result.BlockRanges.end(),
- uint64_t(0u),
- [&](uint64_t Current, const BlockRangeDescriptor& Range) {
- PartialBlockIndexes.insert(Range.BlockIndex);
- return Current + Range.RangeLength;
- });
-
- uint64_t FullBlocksTotalSize =
- std::accumulate(Result.FullBlockIndexes.begin(),
- Result.FullBlockIndexes.end(),
- uint64_t(0u),
- [&](uint64_t Current, uint32_t BlockIndex) {
- const ChunkBlockDescription& BlockDescription = m_BlockDescriptions[BlockIndex];
- uint32_t CurrentOffset =
- gsl::narrow<uint32_t>(CompressedBuffer::GetHeaderSizeForNoneEncoder() + BlockDescription.HeaderSize);
-
- return Current + std::accumulate(BlockDescription.ChunkCompressedLengths.begin(),
- BlockDescription.ChunkCompressedLengths.end(),
- std::uint64_t(CurrentOffset));
- });
-
- uint64_t PartialBlockRequestCount = Result.BlockRanges.size();
- uint64_t PartialBlockCount = PartialBlockIndexes.size();
-
- uint64_t TotalExtraPartialBlocksRequestCount = PartialBlockRequestCount - PartialBlockCount;
- uint64_t ActualPartialDownloadTotalSize = FullBlocksTotalSize + PartialBlocksTotalSize;
-
- uint64_t IdealSkippedSize = AllBlocksTotalBlocksSize - IdealDownloadTotalSize;
- uint64_t ActualSkippedSize = AllBlocksTotalBlocksSize - ActualPartialDownloadTotalSize;
-
- double PercentOfIdealPartialSkippedSize = (ActualSkippedSize * 100.0) / IdealSkippedSize;
-
- ZEN_OPERATION_LOG_INFO(m_LogOutput,
- "Analysis of partial block requests saves download of {} out of {}, {:.1f}% of possible {} using {} extra "
- "requests. Completed in {}",
- NiceBytes(ActualSkippedSize),
- NiceBytes(AllBlocksTotalBlocksSize),
- PercentOfIdealPartialSkippedSize,
- NiceBytes(IdealSkippedSize),
- TotalExtraPartialBlocksRequestCount,
- NiceTimeSpanMs(PartialAnalisysTimer.GetElapsedTimeMs()));
- }
-
- return Result;
-}
-
-ChunkBlockAnalyser::BlockRangeDescriptor
-ChunkBlockAnalyser::MergeBlockRanges(std::span<const BlockRangeDescriptor> Ranges)
-{
- ZEN_ASSERT(Ranges.size() > 1);
- const BlockRangeDescriptor& First = Ranges.front();
- const BlockRangeDescriptor& Last = Ranges.back();
-
- return BlockRangeDescriptor{.BlockIndex = First.BlockIndex,
- .RangeStart = First.RangeStart,
- .RangeLength = Last.RangeStart + Last.RangeLength - First.RangeStart,
- .ChunkBlockIndexStart = First.ChunkBlockIndexStart,
- .ChunkBlockIndexCount = Last.ChunkBlockIndexStart + Last.ChunkBlockIndexCount - First.ChunkBlockIndexStart};
-}
-
-std::optional<std::vector<ChunkBlockAnalyser::BlockRangeDescriptor>>
-ChunkBlockAnalyser::MakeOptionalBlockRangeVector(uint64_t TotalBlockSize, const BlockRangeDescriptor& Range)
-{
- if (Range.RangeLength == TotalBlockSize)
- {
- return {};
- }
- else
- {
- return std::vector<BlockRangeDescriptor>{Range};
- }
-};
-
-const ChunkBlockAnalyser::BlockRangeLimit*
-ChunkBlockAnalyser::GetBlockRangeLimitForRange(std::span<const BlockRangeLimit> Limits,
- uint64_t TotalBlockSize,
- std::span<const BlockRangeDescriptor> Ranges)
-{
- if (Ranges.size() > 1)
- {
- const std::uint64_t WantedSize =
- std::accumulate(Ranges.begin(), Ranges.end(), uint64_t(0), [](uint64_t Current, const BlockRangeDescriptor& Range) {
- return Current + Range.RangeLength;
- });
-
- const double RangeRequestedPercent = (WantedSize * 100.0) / TotalBlockSize;
-
- for (const BlockRangeLimit& Limit : Limits)
- {
- if (RangeRequestedPercent >= Limit.SizePercent && Ranges.size() > Limit.MaxRangeCount)
+ if (ExactRangesSize < FullDownloadSize)
{
- return &Limit;
+ ZEN_DEBUG("Block {}: Full: {}, Ideal: {}, Actual: {}, Saves: {}",
+ NeededBlock.BlockIndex,
+ NiceBytes(FullDownloadSize),
+ NiceBytes(ExactRangesSize),
+ NiceBytes(DownloadRangesSize),
+ NiceBytes(FullDownloadSize - DownloadRangesSize));
}
}
- }
- return nullptr;
-};
-
-std::vector<ChunkBlockAnalyser::BlockRangeDescriptor>
-ChunkBlockAnalyser::CollapseBlockRanges(const uint64_t AlwaysAcceptableGap, std::span<const BlockRangeDescriptor> BlockRanges)
-{
- ZEN_ASSERT(BlockRanges.size() > 1);
- std::vector<BlockRangeDescriptor> CollapsedBlockRanges;
-
- auto BlockRangesIt = BlockRanges.begin();
- CollapsedBlockRanges.push_back(*BlockRangesIt++);
- for (; BlockRangesIt != BlockRanges.end(); BlockRangesIt++)
- {
- BlockRangeDescriptor& LastRange = CollapsedBlockRanges.back();
-
- const uint64_t BothRangeSize = BlockRangesIt->RangeLength + LastRange.RangeLength;
-
- const uint64_t Gap = BlockRangesIt->RangeStart - (LastRange.RangeStart + LastRange.RangeLength);
- if (Gap <= Max(BothRangeSize / 16, AlwaysAcceptableGap))
- {
- LastRange.ChunkBlockIndexCount =
- (BlockRangesIt->ChunkBlockIndexStart + BlockRangesIt->ChunkBlockIndexCount) - LastRange.ChunkBlockIndexStart;
- LastRange.RangeLength = (BlockRangesIt->RangeStart + BlockRangesIt->RangeLength) - LastRange.RangeStart;
- }
- else
+ uint64_t Actual = FullDownloadTotalSize - ActualDownloadTotalSize;
+ uint64_t Ideal = FullDownloadTotalSize - IdealDownloadTotalSize;
+ if (Ideal < FullDownloadTotalSize && !m_Options.IsQuiet)
{
- CollapsedBlockRanges.push_back(*BlockRangesIt);
+ const double AchievedPercent = Ideal == 0 ? 100.0 : (100.0 * Actual) / Ideal;
+ ZEN_INFO(
+ "Block Partial Analysis: Blocks: {}, Full: {}, Ideal: {}, Actual: {}. Skipping {} ({:.1f}%) out of "
+ "possible {} using {} extra ranges "
+ "via {} extra requests. Completed in {}",
+ NeededBlocks.size(),
+ NiceBytes(FullDownloadTotalSize),
+ NiceBytes(IdealDownloadTotalSize),
+ NiceBytes(ActualDownloadTotalSize),
+ NiceBytes(FullDownloadTotalSize - ActualDownloadTotalSize),
+ AchievedPercent,
+ NiceBytes(Ideal),
+ RangeCount - MinRequestCount,
+ RequestCount - MinRequestCount,
+ NiceTimeSpanMs(PartialAnalisysTimer.GetElapsedTimeMs()));
}
}
- return CollapsedBlockRanges;
-};
-
-uint64_t
-ChunkBlockAnalyser::CalculateNextGap(const uint64_t AlwaysAcceptableGap, std::span<const BlockRangeDescriptor> BlockRanges)
-{
- ZEN_ASSERT(BlockRanges.size() > 1);
- uint64_t AcceptableGap = (uint64_t)-1;
- for (size_t RangeIndex = 0; RangeIndex < BlockRanges.size() - 1; RangeIndex++)
- {
- const BlockRangeDescriptor& Range = BlockRanges[RangeIndex];
- const BlockRangeDescriptor& NextRange = BlockRanges[RangeIndex + 1];
-
- const uint64_t Gap = NextRange.RangeStart - (Range.RangeStart + Range.RangeLength);
- AcceptableGap = Min(Gap, AcceptableGap);
- }
- AcceptableGap = RoundUp(AcceptableGap, AlwaysAcceptableGap);
- return AcceptableGap;
-};
-
-std::optional<std::vector<ChunkBlockAnalyser::BlockRangeDescriptor>>
-ChunkBlockAnalyser::CalculateBlockRanges(uint32_t BlockIndex,
- const ChunkBlockDescription& BlockDescription,
- std::span<const uint32_t> BlockChunkIndexNeeded,
- EPartialBlockDownloadMode PartialBlockDownloadMode,
- const uint64_t ChunkStartOffsetInBlock,
- const uint64_t TotalBlockSize,
- uint64_t& OutTotalWantedChunksSize)
-{
- ZEN_TRACE_CPU("CalculateBlockRanges");
-
- if (PartialBlockDownloadMode == EPartialBlockDownloadMode::Off)
- {
- return {};
- }
-
- std::vector<BlockRangeDescriptor> BlockRanges;
- {
- uint64_t CurrentOffset = ChunkStartOffsetInBlock;
- uint32_t ChunkBlockIndex = 0;
- uint32_t NeedBlockChunkIndexOffset = 0;
- BlockRangeDescriptor NextRange{.BlockIndex = BlockIndex};
- while (NeedBlockChunkIndexOffset < BlockChunkIndexNeeded.size() && ChunkBlockIndex < BlockDescription.ChunkRawHashes.size())
- {
- const uint32_t ChunkCompressedLength = BlockDescription.ChunkCompressedLengths[ChunkBlockIndex];
- if (ChunkBlockIndex < BlockChunkIndexNeeded[NeedBlockChunkIndexOffset])
- {
- if (NextRange.RangeLength > 0)
- {
- BlockRanges.push_back(NextRange);
- NextRange = {.BlockIndex = BlockIndex};
- }
- ChunkBlockIndex++;
- CurrentOffset += ChunkCompressedLength;
- }
- else if (ChunkBlockIndex == BlockChunkIndexNeeded[NeedBlockChunkIndexOffset])
- {
- if (NextRange.RangeLength == 0)
- {
- NextRange.RangeStart = CurrentOffset;
- NextRange.ChunkBlockIndexStart = ChunkBlockIndex;
- }
- NextRange.RangeLength += ChunkCompressedLength;
- NextRange.ChunkBlockIndexCount++;
- ChunkBlockIndex++;
- CurrentOffset += ChunkCompressedLength;
- NeedBlockChunkIndexOffset++;
- }
- else
- {
- ZEN_ASSERT(false);
- }
- }
- if (NextRange.RangeLength > 0)
- {
- BlockRanges.push_back(NextRange);
- }
- }
- ZEN_ASSERT(!BlockRanges.empty());
-
- OutTotalWantedChunksSize =
- std::accumulate(BlockRanges.begin(), BlockRanges.end(), uint64_t(0), [](uint64_t Current, const BlockRangeDescriptor& Range) {
- return Current + Range.RangeLength;
- });
-
- double RangeWantedPercent = (OutTotalWantedChunksSize * 100.0) / TotalBlockSize;
-
- if (BlockRanges.size() == 1)
- {
- if (m_Options.IsVerbose)
- {
- ZEN_OPERATION_LOG_INFO(m_LogOutput,
- "Range request of {} ({:.2f}%) using single range from block {} ({}) as is",
- NiceBytes(OutTotalWantedChunksSize),
- RangeWantedPercent,
- BlockDescription.BlockHash,
- NiceBytes(TotalBlockSize));
- }
- return BlockRanges;
- }
-
- if (PartialBlockDownloadMode == EPartialBlockDownloadMode::Exact)
- {
- if (m_Options.IsVerbose)
- {
- ZEN_OPERATION_LOG_INFO(m_LogOutput,
- "Range request of {} ({:.2f}%) using {} ranges from block {} ({})",
- NiceBytes(OutTotalWantedChunksSize),
- RangeWantedPercent,
- BlockRanges.size(),
- BlockDescription.BlockHash,
- NiceBytes(TotalBlockSize));
- }
- return BlockRanges;
- }
-
- if (PartialBlockDownloadMode == EPartialBlockDownloadMode::SingleRange)
- {
- const BlockRangeDescriptor MergedRange = MergeBlockRanges(BlockRanges);
- if (m_Options.IsVerbose)
- {
- const double RangeRequestedPercent = (MergedRange.RangeLength * 100.0) / TotalBlockSize;
- const double WastedPercent = ((MergedRange.RangeLength - OutTotalWantedChunksSize) * 100.0) / MergedRange.RangeLength;
-
- ZEN_OPERATION_LOG_INFO(
- m_LogOutput,
- "Range request of {} ({:.2f}%) using {} ranges from block {} ({}) limited to single block range {} ({:.2f}%) wasting "
- "{:.2f}% ({})",
- NiceBytes(OutTotalWantedChunksSize),
- RangeWantedPercent,
- BlockRanges.size(),
- BlockDescription.BlockHash,
- NiceBytes(TotalBlockSize),
- NiceBytes(MergedRange.RangeLength),
- RangeRequestedPercent,
- WastedPercent,
- NiceBytes(MergedRange.RangeLength - OutTotalWantedChunksSize));
- }
- return MakeOptionalBlockRangeVector(TotalBlockSize, MergedRange);
- }
-
- if (RangeWantedPercent > FullBlockRangePercentLimit)
- {
- const BlockRangeDescriptor MergedRange = MergeBlockRanges(BlockRanges);
- if (m_Options.IsVerbose)
- {
- const double RangeRequestedPercent = (MergedRange.RangeLength * 100.0) / TotalBlockSize;
- const double WastedPercent = ((MergedRange.RangeLength - OutTotalWantedChunksSize) * 100.0) / MergedRange.RangeLength;
-
- ZEN_OPERATION_LOG_INFO(
- m_LogOutput,
- "Range request of {} ({:.2f}%) using {} ranges from block {} ({}) exceeds {}%. Merged to single block range {} "
- "({:.2f}%) wasting {:.2f}% ({})",
- NiceBytes(OutTotalWantedChunksSize),
- RangeWantedPercent,
- BlockRanges.size(),
- BlockDescription.BlockHash,
- NiceBytes(TotalBlockSize),
- FullBlockRangePercentLimit,
- NiceBytes(MergedRange.RangeLength),
- RangeRequestedPercent,
- WastedPercent,
- NiceBytes(MergedRange.RangeLength - OutTotalWantedChunksSize));
- }
- return MakeOptionalBlockRangeVector(TotalBlockSize, MergedRange);
- }
-
- const uint64_t AlwaysAcceptableGap = 4u * 1024u;
-
- std::vector<BlockRangeDescriptor> CollapsedBlockRanges = CollapseBlockRanges(AlwaysAcceptableGap, BlockRanges);
- while (GetBlockRangeLimitForRange(ForceMergeLimits, TotalBlockSize, CollapsedBlockRanges))
- {
- CollapsedBlockRanges = CollapseBlockRanges(CalculateNextGap(AlwaysAcceptableGap, CollapsedBlockRanges), CollapsedBlockRanges);
- }
-
- const std::uint64_t WantedCollapsedSize =
- std::accumulate(CollapsedBlockRanges.begin(),
- CollapsedBlockRanges.end(),
- uint64_t(0),
- [](uint64_t Current, const BlockRangeDescriptor& Range) { return Current + Range.RangeLength; });
-
- const double CollapsedRangeRequestedPercent = (WantedCollapsedSize * 100.0) / TotalBlockSize;
-
- if (m_Options.IsVerbose)
- {
- const double WastedPercent = ((WantedCollapsedSize - OutTotalWantedChunksSize) * 100.0) / WantedCollapsedSize;
-
- ZEN_OPERATION_LOG_INFO(
- m_LogOutput,
- "Range request of {} ({:.2f}%) using {} ranges from block {} ({}) collapsed to {} {:.2f}% using {} ranges wasting {:.2f}% "
- "({})",
- NiceBytes(OutTotalWantedChunksSize),
- RangeWantedPercent,
- BlockRanges.size(),
- BlockDescription.BlockHash,
- NiceBytes(TotalBlockSize),
- NiceBytes(WantedCollapsedSize),
- CollapsedRangeRequestedPercent,
- CollapsedBlockRanges.size(),
- WastedPercent,
- NiceBytes(WantedCollapsedSize - OutTotalWantedChunksSize));
- }
- return CollapsedBlockRanges;
+ return Result;
}
#if ZEN_WITH_TESTS
-namespace testutils {
+namespace chunkblock_testutils {
static std::vector<std::pair<Oid, CompressedBuffer>> CreateAttachments(
const std::span<const size_t>& Sizes,
OodleCompressionLevel CompressionLevel = OodleCompressionLevel::VeryFast,
@@ -1045,12 +934,14 @@ namespace testutils {
return Result;
}
-} // namespace testutils
+} // namespace chunkblock_testutils
+
+TEST_SUITE_BEGIN("remotestore.chunkblock");
TEST_CASE("chunkblock.block")
{
using namespace std::literals;
- using namespace testutils;
+ using namespace chunkblock_testutils;
std::vector<std::size_t> AttachmentSizes({7633, 6825, 5738, 8031, 7225, 566, 3656, 6006, 24, 3466, 1093, 4269, 2257, 3685, 3489,
7194, 6151, 5482, 6217, 3511, 6738, 5061, 7537, 2759, 1916, 8210, 2235, 4024, 1582, 5251,
@@ -1062,8 +953,8 @@ TEST_CASE("chunkblock.block")
for (const auto& It : AttachmentsWithId)
{
Chunks.push_back(
- std::make_pair(It.second.DecodeRawHash(), [Buffer = It.second](const IoHash&) -> std::pair<uint64_t, CompressedBuffer> {
- return {Buffer.DecodeRawSize(), Buffer};
+ std::make_pair(It.second.DecodeRawHash(), [Buffer = It.second](const IoHash&) -> std::pair<uint64_t, CompositeBuffer> {
+ return {Buffer.DecodeRawSize(), Buffer.GetCompressed()};
}));
}
ChunkBlockDescription Block;
@@ -1078,7 +969,7 @@ TEST_CASE("chunkblock.block")
TEST_CASE("chunkblock.reuseblocks")
{
using namespace std::literals;
- using namespace testutils;
+ using namespace chunkblock_testutils;
std::vector<std::vector<std::size_t>> BlockAttachmentSizes(
{std::vector<std::size_t>{7633, 6825, 5738, 8031, 7225, 566, 3656, 6006, 24, 3466, 1093, 4269, 2257, 3685, 3489,
@@ -1097,8 +988,8 @@ TEST_CASE("chunkblock.reuseblocks")
for (const auto& It : AttachmentsWithId)
{
Chunks.push_back(
- std::make_pair(It.second.DecodeRawHash(), [Buffer = It.second](const IoHash&) -> std::pair<uint64_t, CompressedBuffer> {
- return {Buffer.DecodeRawSize(), Buffer};
+ std::make_pair(It.second.DecodeRawHash(), [Buffer = It.second](const IoHash&) -> std::pair<uint64_t, CompositeBuffer> {
+ return {Buffer.DecodeRawSize(), Buffer.GetCompressed()};
}));
}
ChunkBlockDescription Block;
@@ -1106,8 +997,7 @@ TEST_CASE("chunkblock.reuseblocks")
BlockDescriptions.emplace_back(std::move(Block));
}
- LoggerRef LogRef = Log();
- std::unique_ptr<OperationLogOutput> LogOutput(CreateStandardLogOutput(LogRef));
+ LoggerRef LogRef = Log();
{
// We use just about all the chunks - should result in use of both blocks
@@ -1124,14 +1014,8 @@ TEST_CASE("chunkblock.reuseblocks")
std::iota(ManyChunkIndexes.begin(), ManyChunkIndexes.end(), 0);
std::vector<uint32_t> UnusedChunkIndexes;
- std::vector<size_t> ReusedBlocks = FindReuseBlocks(*LogOutput,
- 80,
- false,
- ReuseBlocksStats,
- BlockDescriptions,
- ManyChunkHashes,
- ManyChunkIndexes,
- UnusedChunkIndexes);
+ std::vector<size_t> ReusedBlocks =
+ FindReuseBlocks(LogRef, 80, false, ReuseBlocksStats, BlockDescriptions, ManyChunkHashes, ManyChunkIndexes, UnusedChunkIndexes);
CHECK_EQ(2u, ReusedBlocks.size());
CHECK_EQ(0u, UnusedChunkIndexes.size());
@@ -1152,7 +1036,7 @@ TEST_CASE("chunkblock.reuseblocks")
std::iota(ManyChunkIndexes.begin(), ManyChunkIndexes.end(), 0);
std::vector<uint32_t> UnusedChunkIndexes;
- std::vector<size_t> ReusedBlocks = FindReuseBlocks(*LogOutput,
+ std::vector<size_t> ReusedBlocks = FindReuseBlocks(LogRef,
80,
false,
ReuseBlocksStats,
@@ -1181,7 +1065,7 @@ TEST_CASE("chunkblock.reuseblocks")
// We use half the chunks - should result in no use of blocks due to 80% limit
std::vector<uint32_t> UnusedChunkIndexes80Percent;
ReuseBlocksStatistics ReuseBlocksStats;
- std::vector<size_t> ReusedBlocks80Percent = FindReuseBlocks(*LogOutput,
+ std::vector<size_t> ReusedBlocks80Percent = FindReuseBlocks(LogRef,
80,
false,
ReuseBlocksStats,
@@ -1197,7 +1081,7 @@ TEST_CASE("chunkblock.reuseblocks")
// We use half the chunks - should result in use of both blocks due to 40% limit
std::vector<uint32_t> UnusedChunkIndexes40Percent;
ReuseBlocksStatistics ReuseBlocksStats;
- std::vector<size_t> ReusedBlocks40Percent = FindReuseBlocks(*LogOutput,
+ std::vector<size_t> ReusedBlocks40Percent = FindReuseBlocks(LogRef,
40,
false,
ReuseBlocksStats,
@@ -1227,7 +1111,7 @@ TEST_CASE("chunkblock.reuseblocks")
// We use half the chunks for first block - should result in use of one blocks due to 80% limit
ReuseBlocksStatistics ReuseBlocksStats;
std::vector<uint32_t> UnusedChunkIndexes80Percent;
- std::vector<size_t> ReusedBlocks80Percent = FindReuseBlocks(*LogOutput,
+ std::vector<size_t> ReusedBlocks80Percent = FindReuseBlocks(LogRef,
80,
false,
ReuseBlocksStats,
@@ -1244,7 +1128,7 @@ TEST_CASE("chunkblock.reuseblocks")
// We use half the chunks - should result in use of both blocks due to 40% limit
ReuseBlocksStatistics ReuseBlocksStats;
std::vector<uint32_t> UnusedChunkIndexes40Percent;
- std::vector<size_t> ReusedBlocks40Percent = FindReuseBlocks(*LogOutput,
+ std::vector<size_t> ReusedBlocks40Percent = FindReuseBlocks(LogRef,
40,
false,
ReuseBlocksStats,
@@ -1283,7 +1167,7 @@ TEST_CASE("chunkblock.reuseblocks")
// We use half the chunks for first block - should result in use of one blocks due to 80% limit
ReuseBlocksStatistics ReuseBlocksStats;
std::vector<uint32_t> UnusedChunkIndexes80Percent;
- std::vector<size_t> ReusedBlocks80Percent = FindReuseBlocks(*LogOutput,
+ std::vector<size_t> ReusedBlocks80Percent = FindReuseBlocks(LogRef,
80,
false,
ReuseBlocksStats,
@@ -1300,7 +1184,7 @@ TEST_CASE("chunkblock.reuseblocks")
// We use half the chunks - should result in use of both blocks due to 40% limit
ReuseBlocksStatistics ReuseBlocksStats;
std::vector<uint32_t> UnusedChunkIndexes40Percent;
- std::vector<size_t> ReusedBlocks40Percent = FindReuseBlocks(*LogOutput,
+ std::vector<size_t> ReusedBlocks40Percent = FindReuseBlocks(LogRef,
40,
false,
ReuseBlocksStats,
@@ -1315,6 +1199,877 @@ TEST_CASE("chunkblock.reuseblocks")
}
}
+namespace chunkblock_analyser_testutils {
+
+ // Build a ChunkBlockDescription without any real payload.
+ // Hashes are derived deterministically from (BlockSeed XOR ChunkIndex) so that the same
+ // seed produces the same hashes - useful for deduplication tests.
+ static ChunkBlockDescription MakeBlockDesc(uint64_t HeaderSize,
+ std::initializer_list<uint32_t> CompressedLengths,
+ uint32_t BlockSeed = 0)
+ {
+ ChunkBlockDescription Desc;
+ Desc.HeaderSize = HeaderSize;
+ uint32_t ChunkIndex = 0;
+ for (uint32_t Length : CompressedLengths)
+ {
+ uint64_t HashInput = uint64_t(BlockSeed ^ ChunkIndex);
+ Desc.ChunkRawHashes.push_back(IoHash::HashBuffer(MemoryView(&HashInput, sizeof(HashInput))));
+ Desc.ChunkRawLengths.push_back(Length);
+ Desc.ChunkCompressedLengths.push_back(Length);
+ ChunkIndex++;
+ }
+ return Desc;
+ }
+
+ // Build the robin_map<IoHash, uint32_t> needed by GetNeeded from a flat list of blocks.
+ // First occurrence of each hash wins; index is assigned sequentially across all blocks.
+ [[maybe_unused]] static tsl::robin_map<IoHash, uint32_t, IoHash::Hasher> MakeHashMap(const std::vector<ChunkBlockDescription>& Blocks)
+ {
+ tsl::robin_map<IoHash, uint32_t, IoHash::Hasher> Result;
+ uint32_t Index = 0;
+ for (const ChunkBlockDescription& Block : Blocks)
+ {
+ for (const IoHash& Hash : Block.ChunkRawHashes)
+ {
+ if (!Result.contains(Hash))
+ {
+ Result.emplace(Hash, Index++);
+ }
+ }
+ }
+ return Result;
+ }
+
+} // namespace chunkblock_analyser_testutils
+
+TEST_CASE("chunkblock.mergecheapestrange.picks_smallest_gap")
+{
+ using RD = chunkblock_impl::RangeDescriptor;
+ // Gap between ranges 0-1 is 50, gap between 1-2 is 150 -> pair 0-1 gets merged
+ std::vector<RD> Ranges = {
+ {.RangeStart = 0, .RangeLength = 100, .ChunkBlockIndexStart = 0, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 150, .RangeLength = 100, .ChunkBlockIndexStart = 1, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 400, .RangeLength = 100, .ChunkBlockIndexStart = 2, .ChunkBlockIndexCount = 1},
+ };
+ chunkblock_impl::MergeCheapestRange(Ranges);
+
+ REQUIRE_EQ(2u, Ranges.size());
+ CHECK_EQ(0u, Ranges[0].RangeStart);
+ CHECK_EQ(250u, Ranges[0].RangeLength); // 150+100
+ CHECK_EQ(0u, Ranges[0].ChunkBlockIndexStart);
+ CHECK_EQ(2u, Ranges[0].ChunkBlockIndexCount);
+ CHECK_EQ(400u, Ranges[1].RangeStart);
+ CHECK_EQ(100u, Ranges[1].RangeLength);
+ CHECK_EQ(2u, Ranges[1].ChunkBlockIndexStart);
+ CHECK_EQ(1u, Ranges[1].ChunkBlockIndexCount);
+}
+
+TEST_CASE("chunkblock.mergecheapestrange.tiebreak_smaller_merged")
+{
+ using RD = chunkblock_impl::RangeDescriptor;
+ // Gap 0-1 == gap 1-2 == 100; merged size 0-1 (250) < merged size 1-2 (350) -> pair 0-1 wins
+ std::vector<RD> Ranges = {
+ {.RangeStart = 0, .RangeLength = 100, .ChunkBlockIndexStart = 0, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 200, .RangeLength = 50, .ChunkBlockIndexStart = 1, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 350, .RangeLength = 200, .ChunkBlockIndexStart = 2, .ChunkBlockIndexCount = 1},
+ };
+ chunkblock_impl::MergeCheapestRange(Ranges);
+
+ REQUIRE_EQ(2u, Ranges.size());
+ // Pair 0-1 merged: start=0, length = (200+50)-0 = 250
+ CHECK_EQ(0u, Ranges[0].RangeStart);
+ CHECK_EQ(250u, Ranges[0].RangeLength);
+ CHECK_EQ(0u, Ranges[0].ChunkBlockIndexStart);
+ CHECK_EQ(2u, Ranges[0].ChunkBlockIndexCount);
+ // Pair 1 unchanged (was index 2)
+ CHECK_EQ(350u, Ranges[1].RangeStart);
+ CHECK_EQ(200u, Ranges[1].RangeLength);
+ CHECK_EQ(2u, Ranges[1].ChunkBlockIndexStart);
+ CHECK_EQ(1u, Ranges[1].ChunkBlockIndexCount);
+}
+
+TEST_CASE("chunkblock.optimizeranges.preserves_ranges_low_latency")
+{
+ using RD = chunkblock_impl::RangeDescriptor;
+ // With MaxRangeCountPerRequest unlimited, RequestCount=1
+ // RequestTimeAsBytes = 100000 * 1 * 0.001 = 100 << slack=7000 -> all ranges preserved
+ std::vector<RD> ExactRanges = {
+ {.RangeStart = 0, .RangeLength = 1000, .ChunkBlockIndexStart = 0, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 2000, .RangeLength = 1000, .ChunkBlockIndexStart = 1, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 4000, .RangeLength = 1000, .ChunkBlockIndexStart = 2, .ChunkBlockIndexCount = 1},
+ };
+ uint64_t TotalBlockSize = 10000;
+ double LatencySec = 0.001;
+ uint64_t SpeedBytesPerSec = 100000;
+ uint64_t MaxRangeCountPerReq = (uint64_t)-1;
+ uint64_t MaxRangesPerBlock = 1024;
+
+ auto Result =
+ chunkblock_impl::OptimizeRanges(TotalBlockSize, ExactRanges, LatencySec, SpeedBytesPerSec, MaxRangeCountPerReq, MaxRangesPerBlock);
+
+ REQUIRE_EQ(3u, Result.size());
+}
+
+TEST_CASE("chunkblock.optimizeranges.falls_back_to_full_block")
+{
+ using RD = chunkblock_impl::RangeDescriptor;
+ // 1 range already; slack=100 < SpeedBytesPerSec*LatencySec=200 -> full block (empty result)
+ std::vector<RD> ExactRanges = {
+ {.RangeStart = 100, .RangeLength = 900, .ChunkBlockIndexStart = 0, .ChunkBlockIndexCount = 3},
+ };
+ uint64_t TotalBlockSize = 1000;
+ double LatencySec = 0.01;
+ uint64_t SpeedBytesPerSec = 20000;
+ uint64_t MaxRangeCountPerReq = (uint64_t)-1;
+ uint64_t MaxRangesPerBlock = 1024;
+
+ auto Result =
+ chunkblock_impl::OptimizeRanges(TotalBlockSize, ExactRanges, LatencySec, SpeedBytesPerSec, MaxRangeCountPerReq, MaxRangesPerBlock);
+
+ CHECK(Result.empty());
+}
+
+TEST_CASE("chunkblock.optimizeranges.maxrangesperblock_clamp")
+{
+ using RD = chunkblock_impl::RangeDescriptor;
+ // 5 input ranges; MaxRangesPerBlock=2 clamps to <=2 before the cost model runs
+ std::vector<RD> ExactRanges = {
+ {.RangeStart = 0, .RangeLength = 100, .ChunkBlockIndexStart = 0, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 300, .RangeLength = 100, .ChunkBlockIndexStart = 1, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 600, .RangeLength = 100, .ChunkBlockIndexStart = 2, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 900, .RangeLength = 100, .ChunkBlockIndexStart = 3, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 1200, .RangeLength = 100, .ChunkBlockIndexStart = 4, .ChunkBlockIndexCount = 1},
+ };
+ uint64_t TotalBlockSize = 5000;
+ double LatencySec = 0.001;
+ uint64_t SpeedBytesPerSec = 100000;
+ uint64_t MaxRangeCountPerReq = (uint64_t)-1;
+ uint64_t MaxRangesPerBlock = 2;
+
+ auto Result =
+ chunkblock_impl::OptimizeRanges(TotalBlockSize, ExactRanges, LatencySec, SpeedBytesPerSec, MaxRangeCountPerReq, MaxRangesPerBlock);
+
+ CHECK(Result.size() <= 2u);
+ CHECK(!Result.empty());
+}
+
+TEST_CASE("chunkblock.optimizeranges.low_maxrangecountperrequest_drives_merge")
+{
+ using RD = chunkblock_impl::RangeDescriptor;
+ // MaxRangeCountPerRequest=1 means RequestCount==RangeCount; high latency drives merging
+ // With MaxRangeCountPerRequest=-1 the same 3 ranges would be preserved (verified by comment below)
+ std::vector<RD> ExactRanges = {
+ {.RangeStart = 100, .RangeLength = 100, .ChunkBlockIndexStart = 0, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 250, .RangeLength = 100, .ChunkBlockIndexStart = 1, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 400, .RangeLength = 100, .ChunkBlockIndexStart = 2, .ChunkBlockIndexCount = 1},
+ };
+ uint64_t TotalBlockSize = 1000;
+ double LatencySec = 1.0;
+ uint64_t SpeedBytesPerSec = 500;
+ // With MaxRangeCountPerRequest=-1: RequestCount=1, RequestTimeAsBytes=500 < slack=700 -> preserved
+ // With MaxRangeCountPerRequest=1: RequestCount=3, RequestTimeAsBytes=1500 > slack=700 -> merged
+ uint64_t MaxRangesPerBlock = 1024;
+
+ auto Unlimited =
+ chunkblock_impl::OptimizeRanges(TotalBlockSize, ExactRanges, LatencySec, SpeedBytesPerSec, (uint64_t)-1, MaxRangesPerBlock);
+ CHECK_EQ(3u, Unlimited.size());
+
+ auto Limited =
+ chunkblock_impl::OptimizeRanges(TotalBlockSize, ExactRanges, LatencySec, SpeedBytesPerSec, uint64_t(1), MaxRangesPerBlock);
+ CHECK(Limited.size() < 3u);
+}
+
+TEST_CASE("chunkblock.optimizeranges.unlimited_rangecountperrequest_no_extra_cost")
+{
+ using RD = chunkblock_impl::RangeDescriptor;
+ // MaxRangeCountPerRequest=-1 -> RequestCount always 1, even with many ranges and high latency
+ std::vector<RD> ExactRanges = {
+ {.RangeStart = 0, .RangeLength = 50, .ChunkBlockIndexStart = 0, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 200, .RangeLength = 50, .ChunkBlockIndexStart = 1, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 400, .RangeLength = 50, .ChunkBlockIndexStart = 2, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 600, .RangeLength = 50, .ChunkBlockIndexStart = 3, .ChunkBlockIndexCount = 1},
+ {.RangeStart = 800, .RangeLength = 50, .ChunkBlockIndexStart = 4, .ChunkBlockIndexCount = 1},
+ };
+ uint64_t TotalBlockSize = 5000;
+ double LatencySec = 0.1;
+ uint64_t SpeedBytesPerSec = 10000; // RequestTimeAsBytes=1000 << slack=4750
+ uint64_t MaxRangeCountPerReq = (uint64_t)-1;
+ uint64_t MaxRangesPerBlock = 1024;
+
+ auto Result =
+ chunkblock_impl::OptimizeRanges(TotalBlockSize, ExactRanges, LatencySec, SpeedBytesPerSec, MaxRangeCountPerReq, MaxRangesPerBlock);
+
+ CHECK_EQ(5u, Result.size());
+}
+
+TEST_CASE("chunkblock.optimizeranges.two_range_direct_merge_path")
+{
+ using RD = chunkblock_impl::RangeDescriptor;
+ // Exactly 2 ranges; cost model demands merge; exercises the RangeCount==2 direct-merge branch
+ // After direct merge -> 1 range with small slack -> full block (empty)
+ std::vector<RD> ExactRanges = {
+ {.RangeStart = 0, .RangeLength = 100, .ChunkBlockIndexStart = 0, .ChunkBlockIndexCount = 2},
+ {.RangeStart = 400, .RangeLength = 100, .ChunkBlockIndexStart = 2, .ChunkBlockIndexCount = 2},
+ };
+ uint64_t TotalBlockSize = 600;
+ double LatencySec = 0.1;
+ uint64_t SpeedBytesPerSec = 5000; // RequestTimeAsBytes=500 > slack=400 on first iter
+ uint64_t MaxRangeCountPerReq = (uint64_t)-1;
+ uint64_t MaxRangesPerBlock = 1024;
+
+ // Iteration 1: RangeCount=2, RequestCount=1, RequestTimeAsBytes=500 > slack=400 -> direct merge
+ // After merge: 1 range [{0,500,0,4}], slack=100 < Speed*Lat=500 -> full block
+ auto Result =
+ chunkblock_impl::OptimizeRanges(TotalBlockSize, ExactRanges, LatencySec, SpeedBytesPerSec, MaxRangeCountPerReq, MaxRangesPerBlock);
+
+ CHECK(Result.empty());
+}
+
+TEST_CASE("chunkblock.getneeded.all_chunks")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ LoggerRef LogRef = Log();
+
+ auto Block = MakeBlockDesc(50, {100, 100, 100, 100});
+ ChunkBlockAnalyser::Options Options;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ auto HashMap = MakeHashMap({Block});
+ auto NeededBlocks = Analyser.GetNeeded(HashMap, [](uint32_t) { return true; });
+
+ REQUIRE_EQ(1u, NeededBlocks.size());
+ CHECK_EQ(0u, NeededBlocks[0].BlockIndex);
+ REQUIRE_EQ(4u, NeededBlocks[0].ChunkIndexes.size());
+ CHECK_EQ(0u, NeededBlocks[0].ChunkIndexes[0]);
+ CHECK_EQ(1u, NeededBlocks[0].ChunkIndexes[1]);
+ CHECK_EQ(2u, NeededBlocks[0].ChunkIndexes[2]);
+ CHECK_EQ(3u, NeededBlocks[0].ChunkIndexes[3]);
+}
+
+TEST_CASE("chunkblock.getneeded.no_chunks")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ LoggerRef LogRef = Log();
+
+ auto Block = MakeBlockDesc(50, {100, 100, 100, 100});
+ ChunkBlockAnalyser::Options Options;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ auto HashMap = MakeHashMap({Block});
+ auto NeededBlocks = Analyser.GetNeeded(HashMap, [](uint32_t) { return false; });
+
+ CHECK(NeededBlocks.empty());
+}
+
+TEST_CASE("chunkblock.getneeded.subset_within_block")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ LoggerRef LogRef = Log();
+
+ auto Block = MakeBlockDesc(50, {100, 100, 100, 100});
+ ChunkBlockAnalyser::Options Options;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ auto HashMap = MakeHashMap({Block});
+ // Indices 0 and 2 are needed; 1 and 3 are not
+ auto NeededBlocks = Analyser.GetNeeded(HashMap, [](uint32_t ChunkIndex) { return ChunkIndex == 0 || ChunkIndex == 2; });
+
+ REQUIRE_EQ(1u, NeededBlocks.size());
+ CHECK_EQ(0u, NeededBlocks[0].BlockIndex);
+ REQUIRE_EQ(2u, NeededBlocks[0].ChunkIndexes.size());
+ CHECK_EQ(0u, NeededBlocks[0].ChunkIndexes[0]);
+ CHECK_EQ(2u, NeededBlocks[0].ChunkIndexes[1]);
+}
+
+TEST_CASE("chunkblock.getneeded.dedup_low_slack_wins")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ LoggerRef LogRef = Log();
+
+ // Block 0: {H0, H1, SharedH, H3} - 3 of 4 needed (H3 not needed); slack = 100
+ // Block 1: {H4, H5, SharedH, H6} - only SharedH needed; slack = 300
+ // Block 0 has less slack -> processed first -> SharedH assigned to block 0
+ IoHash SharedH = IoHash::HashBuffer(MemoryView("shared_chunk_dedup", 18));
+ IoHash H0 = IoHash::HashBuffer(MemoryView("block0_chunk0", 13));
+ IoHash H1 = IoHash::HashBuffer(MemoryView("block0_chunk1", 13));
+ IoHash H3 = IoHash::HashBuffer(MemoryView("block0_chunk3", 13));
+ IoHash H4 = IoHash::HashBuffer(MemoryView("block1_chunk0", 13));
+ IoHash H5 = IoHash::HashBuffer(MemoryView("block1_chunk1", 13));
+ IoHash H6 = IoHash::HashBuffer(MemoryView("block1_chunk3", 13));
+
+ ChunkBlockDescription Block0;
+ Block0.HeaderSize = 50;
+ Block0.ChunkRawHashes = {H0, H1, SharedH, H3};
+ Block0.ChunkRawLengths = {100, 100, 100, 100};
+ Block0.ChunkCompressedLengths = {100, 100, 100, 100};
+
+ ChunkBlockDescription Block1;
+ Block1.HeaderSize = 50;
+ Block1.ChunkRawHashes = {H4, H5, SharedH, H6};
+ Block1.ChunkRawLengths = {100, 100, 100, 100};
+ Block1.ChunkCompressedLengths = {100, 100, 100, 100};
+
+ std::vector<ChunkBlockDescription> Blocks = {Block0, Block1};
+ ChunkBlockAnalyser::Options Options;
+ ChunkBlockAnalyser Analyser(LogRef, Blocks, Options);
+
+ // Map: H0->0, H1->1, SharedH->2, H3->3, H4->4, H5->5, H6->6
+ auto HashMap = MakeHashMap(Blocks);
+ // Need H0(0), H1(1), SharedH(2) from block 0; SharedH from block 1 (already index 2)
+ // H3(3) not needed; H4,H5,H6 not needed
+ auto NeededBlocks = Analyser.GetNeeded(HashMap, [](uint32_t ChunkIndex) { return ChunkIndex <= 2; });
+
+ // Block 0 slack=100 (H3 unused), block 1 slack=300 (H4,H5,H6 unused)
+ // Block 0 processed first; picks up H0, H1, SharedH
+ // Block 1 tries SharedH but it's already picked up -> empty -> not added
+ REQUIRE_EQ(1u, NeededBlocks.size());
+ CHECK_EQ(0u, NeededBlocks[0].BlockIndex);
+ REQUIRE_EQ(3u, NeededBlocks[0].ChunkIndexes.size());
+ CHECK_EQ(0u, NeededBlocks[0].ChunkIndexes[0]);
+ CHECK_EQ(1u, NeededBlocks[0].ChunkIndexes[1]);
+ CHECK_EQ(2u, NeededBlocks[0].ChunkIndexes[2]);
+}
+
+TEST_CASE("chunkblock.getneeded.dedup_no_double_pickup")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ LoggerRef LogRef = Log();
+
+ // SharedH appears in both blocks; should appear in the result exactly once
+ IoHash SharedH = IoHash::HashBuffer(MemoryView("shared_chunk_nodup", 18));
+ IoHash H0 = IoHash::HashBuffer(MemoryView("unique_chunk_b0", 15));
+ IoHash H1 = IoHash::HashBuffer(MemoryView("unique_chunk_b1a", 16));
+ IoHash H2 = IoHash::HashBuffer(MemoryView("unique_chunk_b1b", 16));
+ IoHash H3 = IoHash::HashBuffer(MemoryView("unique_chunk_b1c", 16));
+
+ ChunkBlockDescription Block0;
+ Block0.HeaderSize = 50;
+ Block0.ChunkRawHashes = {SharedH, H0};
+ Block0.ChunkRawLengths = {100, 100};
+ Block0.ChunkCompressedLengths = {100, 100};
+
+ ChunkBlockDescription Block1;
+ Block1.HeaderSize = 50;
+ Block1.ChunkRawHashes = {H1, H2, H3, SharedH};
+ Block1.ChunkRawLengths = {100, 100, 100, 100};
+ Block1.ChunkCompressedLengths = {100, 100, 100, 100};
+
+ std::vector<ChunkBlockDescription> Blocks = {Block0, Block1};
+ ChunkBlockAnalyser::Options Options;
+ ChunkBlockAnalyser Analyser(LogRef, Blocks, Options);
+
+ // Map: SharedH->0, H0->1, H1->2, H2->3, H3->4
+ // Only SharedH (index 0) needed; no other chunks
+ auto HashMap = MakeHashMap(Blocks);
+ auto NeededBlocks = Analyser.GetNeeded(HashMap, [](uint32_t ChunkIndex) { return ChunkIndex == 0; });
+
+ // Block 0: SharedH needed, H0 not needed -> slack=100
+ // Block 1: SharedH needed, H1/H2/H3 not needed -> slack=300
+ // Block 0 processed first -> picks up SharedH; Block 1 skips it
+
+ // Count total occurrences of SharedH across all NeededBlocks
+ uint32_t SharedOccurrences = 0;
+ for (const auto& NB : NeededBlocks)
+ {
+ for (uint32_t Idx : NB.ChunkIndexes)
+ {
+ // SharedH is at block-local index 0 in Block0 and index 3 in Block1
+ (void)Idx;
+ SharedOccurrences++;
+ }
+ }
+ CHECK_EQ(1u, SharedOccurrences);
+ REQUIRE_EQ(1u, NeededBlocks.size());
+ CHECK_EQ(0u, NeededBlocks[0].BlockIndex);
+}
+
+TEST_CASE("chunkblock.getneeded.skips_unrequested_chunks")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ LoggerRef LogRef = Log();
+
+ // Block has 4 chunks but only 2 appear in the hash map -> ChunkIndexes has exactly those 2
+ auto Block = MakeBlockDesc(50, {100, 100, 100, 100});
+ ChunkBlockAnalyser::Options Options;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ // Only put chunks at positions 0 and 2 in the map
+ tsl::robin_map<IoHash, uint32_t, IoHash::Hasher> HashMap;
+ HashMap.emplace(Block.ChunkRawHashes[0], 0u);
+ HashMap.emplace(Block.ChunkRawHashes[2], 1u);
+
+ auto NeededBlocks = Analyser.GetNeeded(HashMap, [](uint32_t) { return true; });
+
+ REQUIRE_EQ(1u, NeededBlocks.size());
+ CHECK_EQ(0u, NeededBlocks[0].BlockIndex);
+ REQUIRE_EQ(2u, NeededBlocks[0].ChunkIndexes.size());
+ CHECK_EQ(0u, NeededBlocks[0].ChunkIndexes[0]);
+ CHECK_EQ(2u, NeededBlocks[0].ChunkIndexes[1]);
+}
+
+TEST_CASE("chunkblock.getneeded.two_blocks_both_contribute")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ LoggerRef LogRef = Log();
+
+ // Block 0: all 4 needed (slack=0); block 1: 3 of 4 needed (slack=100)
+ // Both blocks contribute chunks -> 2 NeededBlocks in result
+ auto Block0 = MakeBlockDesc(50, {100, 100, 100, 100}, /*BlockSeed=*/0);
+ auto Block1 = MakeBlockDesc(50, {100, 100, 100, 100}, /*BlockSeed=*/200);
+
+ std::vector<ChunkBlockDescription> Blocks = {Block0, Block1};
+ ChunkBlockAnalyser::Options Options;
+ ChunkBlockAnalyser Analyser(LogRef, Blocks, Options);
+
+ // HashMap: Block0 hashes -> indices 0-3, Block1 hashes -> indices 4-7
+ auto HashMap = MakeHashMap(Blocks);
+ // Need all Block0 chunks (0-3) and Block1 chunks 0-2 (indices 4-6); not chunk index 7 (Block1 chunk 3)
+ auto NeededBlocks = Analyser.GetNeeded(HashMap, [](uint32_t ChunkIndex) { return ChunkIndex <= 6; });
+
+ CHECK_EQ(2u, NeededBlocks.size());
+ // Block 0 has slack=0 (all 4 needed), Block 1 has slack=100 (1 not needed)
+ // Block 0 comes first in result
+ CHECK_EQ(0u, NeededBlocks[0].BlockIndex);
+ CHECK_EQ(4u, NeededBlocks[0].ChunkIndexes.size());
+ CHECK_EQ(1u, NeededBlocks[1].BlockIndex);
+ CHECK_EQ(3u, NeededBlocks[1].ChunkIndexes.size());
+}
+
+TEST_CASE("chunkblock.calc.off_mode")
+{
+ using namespace chunkblock_analyser_testutils;
+ using Mode = ChunkBlockAnalyser::EPartialBlockDownloadMode;
+
+ LoggerRef LogRef = Log();
+
+ // HeaderSize > 0, chunks size matches -> CanDoPartialBlockDownload = true
+ // But mode Off forces full block regardless
+ auto Block = MakeBlockDesc(50, {100, 200, 300, 400});
+ ChunkBlockAnalyser::Options Options;
+ Options.IsQuiet = true;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ std::vector<ChunkBlockAnalyser::NeededBlock> NeededBlocks = {{.BlockIndex = 0, .ChunkIndexes = {0, 2}}};
+ std::vector<Mode> Modes = {Mode::Off};
+
+ auto Result = Analyser.CalculatePartialBlockDownloads(NeededBlocks, Modes);
+
+ REQUIRE_EQ(1u, Result.FullBlockIndexes.size());
+ CHECK_EQ(0u, Result.FullBlockIndexes[0]);
+ CHECK(Result.BlockRanges.empty());
+}
+
+TEST_CASE("chunkblock.calc.exact_mode")
+{
+ using namespace chunkblock_analyser_testutils;
+ using Mode = ChunkBlockAnalyser::EPartialBlockDownloadMode;
+
+ LoggerRef LogRef = Log();
+
+ auto Block = MakeBlockDesc(50, {100, 200, 300, 400});
+ ChunkBlockAnalyser::Options Options;
+ Options.IsQuiet = true;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ uint64_t ChunkStartOffset = CompressedBuffer::GetHeaderSizeForNoneEncoder() + Block.HeaderSize;
+
+ // Need chunks 0 and 2 -> 2 non-contiguous ranges; Exact mode passes them straight through
+ std::vector<ChunkBlockAnalyser::NeededBlock> NeededBlocks = {{.BlockIndex = 0, .ChunkIndexes = {0, 2}}};
+ std::vector<Mode> Modes = {Mode::Exact};
+
+ auto Result = Analyser.CalculatePartialBlockDownloads(NeededBlocks, Modes);
+
+ CHECK(Result.FullBlockIndexes.empty());
+ REQUIRE_EQ(2u, Result.BlockRanges.size());
+
+ CHECK_EQ(0u, Result.BlockRanges[0].BlockIndex);
+ CHECK_EQ(ChunkStartOffset, Result.BlockRanges[0].RangeStart);
+ CHECK_EQ(100u, Result.BlockRanges[0].RangeLength);
+ CHECK_EQ(0u, Result.BlockRanges[0].ChunkBlockIndexStart);
+ CHECK_EQ(1u, Result.BlockRanges[0].ChunkBlockIndexCount);
+
+ CHECK_EQ(0u, Result.BlockRanges[1].BlockIndex);
+ CHECK_EQ(ChunkStartOffset + 300u, Result.BlockRanges[1].RangeStart); // 100+200 before chunk 2
+ CHECK_EQ(300u, Result.BlockRanges[1].RangeLength);
+ CHECK_EQ(2u, Result.BlockRanges[1].ChunkBlockIndexStart);
+ CHECK_EQ(1u, Result.BlockRanges[1].ChunkBlockIndexCount);
+}
+
+TEST_CASE("chunkblock.calc.singlerange_mode")
+{
+ using namespace chunkblock_analyser_testutils;
+ using Mode = ChunkBlockAnalyser::EPartialBlockDownloadMode;
+
+ LoggerRef LogRef = Log();
+
+ auto Block = MakeBlockDesc(50, {100, 200, 300, 400});
+ // Default HostLatencySec=-1 -> OptimizeRanges not called after SingleRange collapse
+ ChunkBlockAnalyser::Options Options;
+ Options.IsQuiet = true;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ uint64_t ChunkStartOffset = CompressedBuffer::GetHeaderSizeForNoneEncoder() + Block.HeaderSize;
+
+ // Need chunks 0 and 2 -> 2 ranges that get collapsed to 1
+ std::vector<ChunkBlockAnalyser::NeededBlock> NeededBlocks = {{.BlockIndex = 0, .ChunkIndexes = {0, 2}}};
+ std::vector<Mode> Modes = {Mode::SingleRange};
+
+ auto Result = Analyser.CalculatePartialBlockDownloads(NeededBlocks, Modes);
+
+ CHECK(Result.FullBlockIndexes.empty());
+ REQUIRE_EQ(1u, Result.BlockRanges.size());
+ CHECK_EQ(0u, Result.BlockRanges[0].BlockIndex);
+ CHECK_EQ(ChunkStartOffset, Result.BlockRanges[0].RangeStart);
+ // Spans from chunk 0 start to chunk 2 end: 100+200+300=600
+ CHECK_EQ(600u, Result.BlockRanges[0].RangeLength);
+ CHECK_EQ(0u, Result.BlockRanges[0].ChunkBlockIndexStart);
+ // ChunkBlockIndexCount = (2+1) - 0 = 3
+ CHECK_EQ(3u, Result.BlockRanges[0].ChunkBlockIndexCount);
+}
+
+TEST_CASE("chunkblock.calc.multirange_mode")
+{
+ using namespace chunkblock_analyser_testutils;
+ using Mode = ChunkBlockAnalyser::EPartialBlockDownloadMode;
+
+ LoggerRef LogRef = Log();
+
+ auto Block = MakeBlockDesc(50, {100, 200, 300, 400});
+ // Low latency: RequestTimeAsBytes=100 << slack -> OptimizeRanges preserves ranges
+ ChunkBlockAnalyser::Options Options;
+ Options.IsQuiet = true;
+ Options.HostLatencySec = 0.001;
+ Options.HostSpeedBytesPerSec = 100000;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ uint64_t ChunkStartOffset = CompressedBuffer::GetHeaderSizeForNoneEncoder() + Block.HeaderSize;
+
+ std::vector<ChunkBlockAnalyser::NeededBlock> NeededBlocks = {{.BlockIndex = 0, .ChunkIndexes = {0, 2}}};
+ std::vector<Mode> Modes = {Mode::MultiRange};
+
+ auto Result = Analyser.CalculatePartialBlockDownloads(NeededBlocks, Modes);
+
+ CHECK(Result.FullBlockIndexes.empty());
+ REQUIRE_EQ(2u, Result.BlockRanges.size());
+ CHECK_EQ(ChunkStartOffset, Result.BlockRanges[0].RangeStart);
+ CHECK_EQ(100u, Result.BlockRanges[0].RangeLength);
+ CHECK_EQ(ChunkStartOffset + 300u, Result.BlockRanges[1].RangeStart);
+ CHECK_EQ(300u, Result.BlockRanges[1].RangeLength);
+}
+
+TEST_CASE("chunkblock.calc.multirangehighspeed_mode")
+{
+ using namespace chunkblock_analyser_testutils;
+ using Mode = ChunkBlockAnalyser::EPartialBlockDownloadMode;
+
+ LoggerRef LogRef = Log();
+
+ auto Block = MakeBlockDesc(50, {100, 200, 300, 400});
+ // Block slack ~= 714 bytes (TotalBlockSize~=1114, RangeTotalSize=400 for chunks 0+2)
+ // RequestTimeAsBytes = 400000 * 1 * 0.001 = 400 < 714 -> ranges preserved
+ ChunkBlockAnalyser::Options Options;
+ Options.IsQuiet = true;
+ Options.HostHighSpeedLatencySec = 0.001;
+ Options.HostHighSpeedBytesPerSec = 400000;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ uint64_t ChunkStartOffset = CompressedBuffer::GetHeaderSizeForNoneEncoder() + Block.HeaderSize;
+
+ std::vector<ChunkBlockAnalyser::NeededBlock> NeededBlocks = {{.BlockIndex = 0, .ChunkIndexes = {0, 2}}};
+ std::vector<Mode> Modes = {Mode::MultiRangeHighSpeed};
+
+ auto Result = Analyser.CalculatePartialBlockDownloads(NeededBlocks, Modes);
+
+ CHECK(Result.FullBlockIndexes.empty());
+ REQUIRE_EQ(2u, Result.BlockRanges.size());
+ CHECK_EQ(ChunkStartOffset, Result.BlockRanges[0].RangeStart);
+ CHECK_EQ(100u, Result.BlockRanges[0].RangeLength);
+ CHECK_EQ(ChunkStartOffset + 300u, Result.BlockRanges[1].RangeStart);
+ CHECK_EQ(300u, Result.BlockRanges[1].RangeLength);
+}
+
+TEST_CASE("chunkblock.calc.all_chunks_needed_full_block")
+{
+ using namespace chunkblock_analyser_testutils;
+ using Mode = ChunkBlockAnalyser::EPartialBlockDownloadMode;
+
+ LoggerRef LogRef = Log();
+
+ auto Block = MakeBlockDesc(50, {100, 200, 300, 400});
+ ChunkBlockAnalyser::Options Options;
+ Options.IsQuiet = true;
+ Options.HostLatencySec = 0.001;
+ Options.HostSpeedBytesPerSec = 100000;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ // All 4 chunks needed -> short-circuit to full block regardless of mode
+ std::vector<ChunkBlockAnalyser::NeededBlock> NeededBlocks = {{.BlockIndex = 0, .ChunkIndexes = {0, 1, 2, 3}}};
+ std::vector<Mode> Modes = {Mode::Exact};
+
+ auto Result = Analyser.CalculatePartialBlockDownloads(NeededBlocks, Modes);
+
+ REQUIRE_EQ(1u, Result.FullBlockIndexes.size());
+ CHECK_EQ(0u, Result.FullBlockIndexes[0]);
+ CHECK(Result.BlockRanges.empty());
+}
+
+TEST_CASE("chunkblock.calc.headersize_zero_forces_full_block")
+{
+ using namespace chunkblock_analyser_testutils;
+ using Mode = ChunkBlockAnalyser::EPartialBlockDownloadMode;
+
+ LoggerRef LogRef = Log();
+
+ // HeaderSize=0 -> CanDoPartialBlockDownload=false -> full block even in Exact mode
+ auto Block = MakeBlockDesc(0, {100, 200, 300, 400});
+ ChunkBlockAnalyser::Options Options;
+ Options.IsQuiet = true;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ std::vector<ChunkBlockAnalyser::NeededBlock> NeededBlocks = {{.BlockIndex = 0, .ChunkIndexes = {0, 2}}};
+ std::vector<Mode> Modes = {Mode::Exact};
+
+ auto Result = Analyser.CalculatePartialBlockDownloads(NeededBlocks, Modes);
+
+ REQUIRE_EQ(1u, Result.FullBlockIndexes.size());
+ CHECK_EQ(0u, Result.FullBlockIndexes[0]);
+ CHECK(Result.BlockRanges.empty());
+}
+
+TEST_CASE("chunkblock.calc.low_maxrangecountperrequest")
+{
+ using namespace chunkblock_analyser_testutils;
+ using Mode = ChunkBlockAnalyser::EPartialBlockDownloadMode;
+
+ LoggerRef LogRef = Log();
+
+ // 5 chunks of 100 bytes each; need chunks 0, 2, 4 -> 3 non-contiguous ranges
+ // With MaxRangeCountPerRequest=1 and high latency, cost model merges aggressively -> full block
+ auto Block = MakeBlockDesc(10, {100, 100, 100, 100, 100});
+ ChunkBlockAnalyser::Options Options;
+ Options.IsQuiet = true;
+ Options.HostLatencySec = 0.1;
+ Options.HostSpeedBytesPerSec = 1000;
+ Options.HostMaxRangeCountPerRequest = 1;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ std::vector<ChunkBlockAnalyser::NeededBlock> NeededBlocks = {{.BlockIndex = 0, .ChunkIndexes = {0, 2, 4}}};
+ std::vector<Mode> Modes = {Mode::MultiRange};
+
+ auto Result = Analyser.CalculatePartialBlockDownloads(NeededBlocks, Modes);
+
+ // Cost model drives merging: 3 requests x 1000 x 0.1 = 300 > slack ~= 210+headersize
+ // After merges converges to full block
+ REQUIRE_EQ(1u, Result.FullBlockIndexes.size());
+ CHECK_EQ(0u, Result.FullBlockIndexes[0]);
+ CHECK(Result.BlockRanges.empty());
+}
+
+TEST_CASE("chunkblock.calc.no_latency_skips_optimize")
+{
+ using namespace chunkblock_analyser_testutils;
+ using Mode = ChunkBlockAnalyser::EPartialBlockDownloadMode;
+
+ LoggerRef LogRef = Log();
+
+ auto Block = MakeBlockDesc(50, {100, 200, 300, 400});
+ // Default HostLatencySec=-1 -> OptimizeRanges not called; raw GetBlockRanges result used
+ ChunkBlockAnalyser::Options Options;
+ Options.IsQuiet = true;
+ ChunkBlockAnalyser Analyser(LogRef, std::span<const ChunkBlockDescription>(&Block, 1), Options);
+
+ uint64_t ChunkStartOffset = CompressedBuffer::GetHeaderSizeForNoneEncoder() + Block.HeaderSize;
+
+ std::vector<ChunkBlockAnalyser::NeededBlock> NeededBlocks = {{.BlockIndex = 0, .ChunkIndexes = {0, 2}}};
+ std::vector<Mode> Modes = {Mode::MultiRange};
+
+ auto Result = Analyser.CalculatePartialBlockDownloads(NeededBlocks, Modes);
+
+ // No optimize pass -> exact ranges from GetBlockRanges
+ CHECK(Result.FullBlockIndexes.empty());
+ REQUIRE_EQ(2u, Result.BlockRanges.size());
+ CHECK_EQ(ChunkStartOffset, Result.BlockRanges[0].RangeStart);
+ CHECK_EQ(100u, Result.BlockRanges[0].RangeLength);
+ CHECK_EQ(ChunkStartOffset + 300u, Result.BlockRanges[1].RangeStart);
+ CHECK_EQ(300u, Result.BlockRanges[1].RangeLength);
+}
+
+TEST_CASE("chunkblock.calc.multiple_blocks_different_modes")
+{
+ using namespace chunkblock_analyser_testutils;
+ using Mode = ChunkBlockAnalyser::EPartialBlockDownloadMode;
+
+ LoggerRef LogRef = Log();
+
+ // 3 blocks with different modes: Off, Exact, MultiRange
+ auto Block0 = MakeBlockDesc(50, {100, 200, 300, 400}, /*BlockSeed=*/0);
+ auto Block1 = MakeBlockDesc(50, {100, 200, 300, 400}, /*BlockSeed=*/10);
+ auto Block2 = MakeBlockDesc(50, {100, 200, 300, 400}, /*BlockSeed=*/20);
+
+ ChunkBlockAnalyser::Options Options;
+ Options.IsQuiet = true;
+ Options.HostLatencySec = 0.001;
+ Options.HostSpeedBytesPerSec = 100000;
+
+ std::vector<ChunkBlockDescription> Blocks = {Block0, Block1, Block2};
+ ChunkBlockAnalyser Analyser(LogRef, Blocks, Options);
+
+ uint64_t ChunkStartOffset = CompressedBuffer::GetHeaderSizeForNoneEncoder() + 50;
+
+ std::vector<ChunkBlockAnalyser::NeededBlock> NeededBlocks = {
+ {.BlockIndex = 0, .ChunkIndexes = {0, 2}},
+ {.BlockIndex = 1, .ChunkIndexes = {0, 2}},
+ {.BlockIndex = 2, .ChunkIndexes = {0, 2}},
+ };
+ std::vector<Mode> Modes = {Mode::Off, Mode::Exact, Mode::MultiRange};
+
+ auto Result = Analyser.CalculatePartialBlockDownloads(NeededBlocks, Modes);
+
+ // Block 0: Off -> FullBlockIndexes
+ REQUIRE_EQ(1u, Result.FullBlockIndexes.size());
+ CHECK_EQ(0u, Result.FullBlockIndexes[0]);
+
+ // Block 1: Exact -> 2 ranges; Block 2: MultiRange (low latency) -> 2 ranges
+ // Total: 4 ranges
+ REQUIRE_EQ(4u, Result.BlockRanges.size());
+
+ // First 2 ranges belong to Block 1 (Exact)
+ CHECK_EQ(1u, Result.BlockRanges[0].BlockIndex);
+ CHECK_EQ(ChunkStartOffset, Result.BlockRanges[0].RangeStart);
+ CHECK_EQ(100u, Result.BlockRanges[0].RangeLength);
+ CHECK_EQ(1u, Result.BlockRanges[1].BlockIndex);
+ CHECK_EQ(ChunkStartOffset + 300u, Result.BlockRanges[1].RangeStart);
+ CHECK_EQ(300u, Result.BlockRanges[1].RangeLength);
+
+ // Last 2 ranges belong to Block 2 (MultiRange preserved)
+ CHECK_EQ(2u, Result.BlockRanges[2].BlockIndex);
+ CHECK_EQ(ChunkStartOffset, Result.BlockRanges[2].RangeStart);
+ CHECK_EQ(100u, Result.BlockRanges[2].RangeLength);
+ CHECK_EQ(2u, Result.BlockRanges[3].BlockIndex);
+ CHECK_EQ(ChunkStartOffset + 300u, Result.BlockRanges[3].RangeStart);
+ CHECK_EQ(300u, Result.BlockRanges[3].RangeLength);
+}
+
+TEST_CASE("chunkblock.getblockranges.first_chunk_only")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ auto Block = MakeBlockDesc(50, {100, 200, 300, 400});
+ uint64_t ChunkStartOffset = CompressedBuffer::GetHeaderSizeForNoneEncoder() + Block.HeaderSize;
+
+ std::vector<uint32_t> Needed = {0};
+ auto Ranges = chunkblock_impl::GetBlockRanges(Block, ChunkStartOffset, Needed);
+
+ REQUIRE_EQ(1u, Ranges.size());
+ CHECK_EQ(ChunkStartOffset, Ranges[0].RangeStart);
+ CHECK_EQ(100u, Ranges[0].RangeLength);
+ CHECK_EQ(0u, Ranges[0].ChunkBlockIndexStart);
+ CHECK_EQ(1u, Ranges[0].ChunkBlockIndexCount);
+}
+
+TEST_CASE("chunkblock.getblockranges.last_chunk_only")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ auto Block = MakeBlockDesc(50, {100, 200, 300, 400});
+ uint64_t ChunkStartOffset = CompressedBuffer::GetHeaderSizeForNoneEncoder() + Block.HeaderSize;
+
+ std::vector<uint32_t> Needed = {3};
+ auto Ranges = chunkblock_impl::GetBlockRanges(Block, ChunkStartOffset, Needed);
+
+ REQUIRE_EQ(1u, Ranges.size());
+ CHECK_EQ(ChunkStartOffset + 600u, Ranges[0].RangeStart); // 100+200+300 before chunk 3
+ CHECK_EQ(400u, Ranges[0].RangeLength);
+ CHECK_EQ(3u, Ranges[0].ChunkBlockIndexStart);
+ CHECK_EQ(1u, Ranges[0].ChunkBlockIndexCount);
+}
+
+TEST_CASE("chunkblock.getblockranges.middle_chunk_only")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ auto Block = MakeBlockDesc(50, {100, 200, 300, 400});
+ uint64_t ChunkStartOffset = CompressedBuffer::GetHeaderSizeForNoneEncoder() + Block.HeaderSize;
+
+ std::vector<uint32_t> Needed = {1};
+ auto Ranges = chunkblock_impl::GetBlockRanges(Block, ChunkStartOffset, Needed);
+
+ REQUIRE_EQ(1u, Ranges.size());
+ CHECK_EQ(ChunkStartOffset + 100u, Ranges[0].RangeStart); // 100 before chunk 1
+ CHECK_EQ(200u, Ranges[0].RangeLength);
+ CHECK_EQ(1u, Ranges[0].ChunkBlockIndexStart);
+ CHECK_EQ(1u, Ranges[0].ChunkBlockIndexCount);
+}
+
+TEST_CASE("chunkblock.getblockranges.all_chunks")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ auto Block = MakeBlockDesc(50, {100, 200, 300, 400});
+ uint64_t ChunkStartOffset = CompressedBuffer::GetHeaderSizeForNoneEncoder() + Block.HeaderSize;
+
+ std::vector<uint32_t> Needed = {0, 1, 2, 3};
+ auto Ranges = chunkblock_impl::GetBlockRanges(Block, ChunkStartOffset, Needed);
+
+ REQUIRE_EQ(1u, Ranges.size());
+ CHECK_EQ(ChunkStartOffset, Ranges[0].RangeStart);
+ CHECK_EQ(1000u, Ranges[0].RangeLength); // 100+200+300+400
+ CHECK_EQ(0u, Ranges[0].ChunkBlockIndexStart);
+ CHECK_EQ(4u, Ranges[0].ChunkBlockIndexCount);
+}
+
+TEST_CASE("chunkblock.getblockranges.non_contiguous")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ // Chunks 0 and 2 needed, chunk 1 skipped -> two separate ranges
+ auto Block = MakeBlockDesc(50, {100, 200, 300});
+ uint64_t ChunkStartOffset = CompressedBuffer::GetHeaderSizeForNoneEncoder() + Block.HeaderSize;
+
+ std::vector<uint32_t> Needed = {0, 2};
+ auto Ranges = chunkblock_impl::GetBlockRanges(Block, ChunkStartOffset, Needed);
+
+ REQUIRE_EQ(2u, Ranges.size());
+
+ CHECK_EQ(ChunkStartOffset, Ranges[0].RangeStart);
+ CHECK_EQ(100u, Ranges[0].RangeLength);
+ CHECK_EQ(0u, Ranges[0].ChunkBlockIndexStart);
+ CHECK_EQ(1u, Ranges[0].ChunkBlockIndexCount);
+
+ CHECK_EQ(ChunkStartOffset + 300u, Ranges[1].RangeStart); // 100+200 before chunk 2
+ CHECK_EQ(300u, Ranges[1].RangeLength);
+ CHECK_EQ(2u, Ranges[1].ChunkBlockIndexStart);
+ CHECK_EQ(1u, Ranges[1].ChunkBlockIndexCount);
+}
+
+TEST_CASE("chunkblock.getblockranges.contiguous_run")
+{
+ using namespace chunkblock_analyser_testutils;
+
+ // Chunks 1, 2, 3 needed (consecutive) -> one merged range
+ auto Block = MakeBlockDesc(50, {50, 100, 150, 200, 250});
+ uint64_t ChunkStartOffset = CompressedBuffer::GetHeaderSizeForNoneEncoder() + Block.HeaderSize;
+
+ std::vector<uint32_t> Needed = {1, 2, 3};
+ auto Ranges = chunkblock_impl::GetBlockRanges(Block, ChunkStartOffset, Needed);
+
+ REQUIRE_EQ(1u, Ranges.size());
+ CHECK_EQ(ChunkStartOffset + 50u, Ranges[0].RangeStart); // 50 before chunk 1
+ CHECK_EQ(450u, Ranges[0].RangeLength); // 100+150+200
+ CHECK_EQ(1u, Ranges[0].ChunkBlockIndexStart);
+ CHECK_EQ(3u, Ranges[0].ChunkBlockIndexCount);
+}
+
+TEST_SUITE_END();
+
void
chunkblock_forcelink()
{
diff --git a/src/zenremotestore/chunking/chunkedcontent.cpp b/src/zenremotestore/chunking/chunkedcontent.cpp
index 26d179f14..c09ab9d3a 100644
--- a/src/zenremotestore/chunking/chunkedcontent.cpp
+++ b/src/zenremotestore/chunking/chunkedcontent.cpp
@@ -166,7 +166,6 @@ namespace {
if (Chunked.Info.ChunkSequence.empty())
{
AddChunkSequence(Stats, OutChunkedContent.ChunkedContent, ChunkHashToChunkIndex, Chunked.Info.RawHash, RawSize);
- Stats.UniqueSequencesFound++;
}
else
{
@@ -186,7 +185,6 @@ namespace {
Chunked.Info.ChunkHashes,
ChunkSizes);
}
- Stats.UniqueSequencesFound++;
}
});
Stats.FilesChunked++;
@@ -253,7 +251,7 @@ FolderContent::operator==(const FolderContent& Rhs) const
if ((Platform == Rhs.Platform) && (RawSizes == Rhs.RawSizes) && (Attributes == Rhs.Attributes) &&
(ModificationTicks == Rhs.ModificationTicks) && (Paths.size() == Rhs.Paths.size()))
{
- size_t PathCount = 0;
+ size_t PathCount = Paths.size();
for (size_t PathIndex = 0; PathIndex < PathCount; PathIndex++)
{
if (Paths[PathIndex].generic_string() != Rhs.Paths[PathIndex].generic_string())
@@ -1706,6 +1704,8 @@ namespace chunkedcontent_testutils {
} // namespace chunkedcontent_testutils
+TEST_SUITE_BEGIN("remotestore.chunkedcontent");
+
TEST_CASE("chunkedcontent.DeletePathsFromContent")
{
FastRandom BaseRandom;
@@ -1924,6 +1924,8 @@ TEST_CASE("chunkedcontent.ApplyChunkedContentOverlay")
}
}
+TEST_SUITE_END();
+
#endif // ZEN_WITH_TESTS
} // namespace zen
diff --git a/src/zenremotestore/chunking/chunkedfile.cpp b/src/zenremotestore/chunking/chunkedfile.cpp
index 652110605..633ddfd0d 100644
--- a/src/zenremotestore/chunking/chunkedfile.cpp
+++ b/src/zenremotestore/chunking/chunkedfile.cpp
@@ -211,6 +211,8 @@ ZEN_THIRD_PARTY_INCLUDES_END
namespace zen {
# if 0
+TEST_SUITE_BEGIN("remotestore.chunkedfile");
+
TEST_CASE("chunkedfile.findparams")
{
# if 1
@@ -513,6 +515,8 @@ TEST_CASE("chunkedfile.findparams")
// WorkLatch.CountDown();
// WorkLatch.Wait();
}
+
+TEST_SUITE_END();
# endif // 0
void
diff --git a/src/zenremotestore/chunking/chunkingcache.cpp b/src/zenremotestore/chunking/chunkingcache.cpp
index 7f0a26330..e9b783a00 100644
--- a/src/zenremotestore/chunking/chunkingcache.cpp
+++ b/src/zenremotestore/chunking/chunkingcache.cpp
@@ -75,13 +75,13 @@ public:
{
Lock.ReleaseNow();
RwLock::ExclusiveLockScope EditLock(m_Lock);
- if (auto RemoveIt = m_PathHashToEntry.find(PathHash); It != m_PathHashToEntry.end())
+ if (auto RemoveIt = m_PathHashToEntry.find(PathHash); RemoveIt != m_PathHashToEntry.end())
{
- CachedEntry& DeleteEntry = m_Entries[It->second];
+ CachedEntry& DeleteEntry = m_Entries[RemoveIt->second];
DeleteEntry.Chunked = {};
DeleteEntry.ModificationTick = 0;
- m_FreeEntryIndexes.push_back(It->second);
- m_PathHashToEntry.erase(It);
+ m_FreeEntryIndexes.push_back(RemoveIt->second);
+ m_PathHashToEntry.erase(RemoveIt);
}
}
}
@@ -461,6 +461,8 @@ namespace chunkingcache_testutils {
}
} // namespace chunkingcache_testutils
+TEST_SUITE_BEGIN("remotestore.chunkingcache");
+
TEST_CASE("chunkingcache.nullchunkingcache")
{
using namespace chunkingcache_testutils;
@@ -617,6 +619,8 @@ TEST_CASE("chunkingcache.diskchunkingcache")
}
}
+TEST_SUITE_END();
+
void
chunkingcache_forcelink()
{
generated by cgit v1.2.3 (git 2.25.1) at 2026-04-26 21:23:49 +0000