| Directory: | cvmfs/ |
|---|---|
| File: | cvmfs/ingestion/chunk_detector.cc |
| Date: | 2025-11-23 02:35:30 |
| Exec | Total | Coverage | |
|---|---|---|---|
| Lines: | 56 | 56 | 100.0% |
| Branches: | 33 | 46 | 71.7% |
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /** | ||
| 2 | * This file is part of the CernVM File System. | ||
| 3 | */ | ||
| 4 | |||
| 5 | |||
| 6 | #include "chunk_detector.h" | ||
| 7 | |||
| 8 | #include <algorithm> | ||
| 9 | #include <cassert> | ||
| 10 | #include <limits> | ||
| 11 | |||
| 12 | #include "ingestion/item.h" | ||
| 13 | |||
| 14 | |||
| 15 | 5325043 | uint64_t ChunkDetector::FindNextCutMark(BlockItem *block) { | |
| 16 | 5325043 | const uint64_t result = DoFindNextCutMark(block); | |
| 17 |
2/2✓ Branch 0 taken 1577278 times.
✓ Branch 1 taken 3747489 times.
|
5324767 | if (result == 0) |
| 18 | 1577278 | offset_ += block->size(); | |
| 19 | 5324721 | return result; | |
| 20 | } | ||
| 21 | |||
| 22 | |||
| 23 | //------------------------------------------------------------------------------ | ||
| 24 | |||
| 25 | |||
| 26 | 3587640 | uint64_t StaticOffsetDetector::DoFindNextCutMark(BlockItem *buffer) { | |
| 27 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 3587640 times.
|
3587640 | assert(buffer->type() == BlockItem::kBlockData); |
| 28 | |||
| 29 | 3587640 | const uint64_t beginning = offset(); | |
| 30 | 3587640 | const uint64_t end = offset() + buffer->size(); | |
| 31 | |||
| 32 | 3587640 | const uint64_t next_cut = last_cut() + chunk_size_; | |
| 33 |
3/4✓ Branch 0 taken 3587640 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 3584035 times.
✓ Branch 3 taken 3605 times.
|
3587640 | if (next_cut >= beginning && next_cut < end) { |
| 34 | 3584035 | return DoCut(next_cut); | |
| 35 | } | ||
| 36 | |||
| 37 | 3605 | return NoCut(next_cut); | |
| 38 | } | ||
| 39 | |||
| 40 | |||
| 41 | //------------------------------------------------------------------------------ | ||
| 42 | |||
| 43 | |||
| 44 | // This defines the center of the interval where the xor32 rolling checksum is | ||
| 45 | // queried. You should never change this number, since it affects the definition | ||
| 46 | // of cut marks. | ||
| 47 | const int32_t Xor32Detector::kMagicNumber = std::numeric_limits<uint32_t>::max() | ||
| 48 | / 2; | ||
| 49 | |||
| 50 | |||
| 51 | 11616581 | Xor32Detector::Xor32Detector(const uint64_t minimal_chunk_size, | |
| 52 | const uint64_t average_chunk_size, | ||
| 53 | 11616581 | const uint64_t maximal_chunk_size) | |
| 54 | 11616581 | : minimal_chunk_size_(minimal_chunk_size) | |
| 55 | 11616581 | , average_chunk_size_(average_chunk_size) | |
| 56 | 11616581 | , maximal_chunk_size_(maximal_chunk_size) | |
| 57 | 26 | , threshold_( | |
| 58 | (average_chunk_size > 0) | ||
| 59 | 11616555 | ? (std::numeric_limits<uint32_t>::max() / average_chunk_size) | |
| 60 | : 0) | ||
| 61 | 11616581 | , xor32_ptr_(0) | |
| 62 |
2/2✓ Branch 1 taken 11616555 times.
✓ Branch 2 taken 26 times.
|
11616581 | , xor32_(0) { |
| 63 |
3/4✓ Branch 0 taken 11616555 times.
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 11616555 times.
|
11616581 | assert((average_chunk_size_ == 0) || (minimal_chunk_size_ > 0)); |
| 64 |
2/2✓ Branch 0 taken 11616555 times.
✓ Branch 1 taken 26 times.
|
11616581 | if (minimal_chunk_size_ > 0) { |
| 65 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 11616555 times.
|
11616555 | assert(minimal_chunk_size_ >= kXor32Window); |
| 66 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 11616555 times.
|
11616555 | assert(minimal_chunk_size_ < average_chunk_size_); |
| 67 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 11616555 times.
|
11616555 | assert(average_chunk_size_ < maximal_chunk_size_); |
| 68 | } | ||
| 69 | 11616581 | } | |
| 70 | |||
| 71 | |||
| 72 | 1737311 | uint64_t Xor32Detector::DoFindNextCutMark(BlockItem *buffer) { | |
| 73 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1737311 times.
|
1737311 | assert(minimal_chunk_size_ > 0); |
| 74 | 1737311 | const unsigned char *data = buffer->data(); | |
| 75 | |||
| 76 | // Get the offset where the next xor32 computation needs to be continued | ||
| 77 | // Note: this could be after collecting at least kMinChunkSize bytes in the | ||
| 78 | // current chunk, or directly at the beginning of the buffer, when a | ||
| 79 | // cut mark is currently searched | ||
| 80 | 1737357 | const uint64_t global_offset = std::max( | |
| 81 | 1737357 | last_cut() + static_cast<uint64_t>(minimal_chunk_size_ - kXor32Window), | |
| 82 | 1737357 | xor32_ptr_); | |
| 83 | |||
| 84 | // Check if the next xor32 computation is taking place in the current buffer | ||
| 85 |
2/2✓ Branch 2 taken 744245 times.
✓ Branch 3 taken 993388 times.
|
1737403 | if (global_offset >= offset() + static_cast<uint64_t>(buffer->size())) { |
| 86 |
1/2✓ Branch 1 taken 744199 times.
✗ Branch 2 not taken.
|
744245 | return NoCut(global_offset); |
| 87 | } | ||
| 88 | |||
| 89 | // get the byte offset in the current buffer | ||
| 90 | 993388 | uint64_t internal_offset = global_offset - offset(); | |
| 91 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 993434 times.
|
993388 | assert(internal_offset < static_cast<uint64_t>(buffer->size())); |
| 92 | |||
| 93 | // Precompute the xor32 rolling checksum for finding the next cut mark | ||
| 94 | // Note: this might be skipped, if the precomputation was already performed | ||
| 95 | // for the current rolling checksum | ||
| 96 | // (internal_precompute_end will be negative --> loop is not entered) | ||
| 97 | 993434 | const uint64_t precompute_end = last_cut() + minimal_chunk_size_; | |
| 98 | 993434 | const int64_t internal_precompute_end = std::min( | |
| 99 | 993434 | static_cast<int64_t>(precompute_end - offset()), | |
| 100 | 993434 | static_cast<int64_t>(buffer->size())); | |
| 101 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 993434 times.
|
993434 | assert(internal_precompute_end - static_cast<int64_t>(internal_offset) |
| 102 | <= static_cast<int64_t>(kXor32Window)); | ||
| 103 |
2/2✓ Branch 0 taken 5248308 times.
✓ Branch 1 taken 993434 times.
|
6241742 | for (; static_cast<int64_t>(internal_offset) < internal_precompute_end; |
| 104 | ++internal_offset) { | ||
| 105 | 5248308 | xor32(data[internal_offset]); | |
| 106 | } | ||
| 107 | |||
| 108 | // Do the actual computation and try to find a xor32 based cut mark | ||
| 109 | // Note: this loop is bound either by kMaxChunkSize or by the size of the | ||
| 110 | // current buffer, thus the computation would continue later | ||
| 111 | 993434 | const uint64_t internal_max_chunk_size_end = last_cut() + maximal_chunk_size_ | |
| 112 | 993434 | - offset(); | |
| 113 | 993342 | const uint64_t internal_compute_end = std::min( | |
| 114 | 993434 | internal_max_chunk_size_end, static_cast<uint64_t>(buffer->size())); | |
| 115 |
2/2✓ Branch 0 taken 19748148070 times.
✓ Branch 1 taken 834186 times.
|
19748982256 | for (; internal_offset < internal_compute_end; ++internal_offset) { |
| 116 | 19748148070 | xor32(data[internal_offset]); | |
| 117 | |||
| 118 | // check if we found a cut mark | ||
| 119 |
2/2✓ Branch 1 taken 159294 times.
✓ Branch 2 taken 19681351428 times.
|
19672424572 | if (CheckThreshold()) { |
| 120 |
1/2✓ Branch 2 taken 159294 times.
✗ Branch 3 not taken.
|
159294 | return DoCut(internal_offset + offset()); |
| 121 | } | ||
| 122 | } | ||
| 123 | |||
| 124 | // Check if the loop was exited because we reached kMaxChunkSize and do a | ||
| 125 | // hard cut in this case. If not, it exited because we ran out of data in this | ||
| 126 | // buffer --> continue computation with the next buffer | ||
| 127 |
2/2✓ Branch 0 taken 4160 times.
✓ Branch 1 taken 830026 times.
|
834186 | if (internal_offset == internal_max_chunk_size_end) { |
| 128 |
1/2✓ Branch 2 taken 4160 times.
✗ Branch 3 not taken.
|
4160 | return DoCut(internal_offset + offset()); |
| 129 | } else { | ||
| 130 |
1/2✓ Branch 2 taken 830026 times.
✗ Branch 3 not taken.
|
830026 | return NoCut(internal_offset + offset()); |
| 131 | } | ||
| 132 | } | ||
| 133 |