| Directory: | cvmfs/ |
|---|---|
| File: | cvmfs/ingestion/chunk_detector.cc |
| Date: | 2026-05-19 11:45:12 |
| 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 | 4961528 | uint64_t ChunkDetector::FindNextCutMark(BlockItem *block) { | |
| 16 | 4961528 | const uint64_t result = DoFindNextCutMark(block); | |
| 17 |
2/2✓ Branch 0 taken 1311986 times.
✓ Branch 1 taken 3649682 times.
|
4961668 | if (result == 0) |
| 18 | 1311986 | offset_ += block->size(); | |
| 19 | 4961612 | return result; | |
| 20 | } | ||
| 21 | |||
| 22 | |||
| 23 | //------------------------------------------------------------------------------ | ||
| 24 | |||
| 25 | |||
| 26 | 3382632 | uint64_t StaticOffsetDetector::DoFindNextCutMark(BlockItem *buffer) { | |
| 27 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 3382632 times.
|
3382632 | assert(buffer->type() == BlockItem::kBlockData); |
| 28 | |||
| 29 | 3382632 | const uint64_t beginning = offset(); | |
| 30 | 3382632 | const uint64_t end = offset() + buffer->size(); | |
| 31 | |||
| 32 | 3382632 | const uint64_t next_cut = last_cut() + chunk_size_; | |
| 33 |
3/4✓ Branch 0 taken 3382632 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 3379233 times.
✓ Branch 3 taken 3399 times.
|
3382632 | if (next_cut >= beginning && next_cut < end) { |
| 34 | 3379233 | return DoCut(next_cut); | |
| 35 | } | ||
| 36 | |||
| 37 | 3399 | 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 | 7098261 | Xor32Detector::Xor32Detector(const uint64_t minimal_chunk_size, | |
| 52 | const uint64_t average_chunk_size, | ||
| 53 | 7098261 | const uint64_t maximal_chunk_size) | |
| 54 | 7098261 | : minimal_chunk_size_(minimal_chunk_size) | |
| 55 | 7098261 | , average_chunk_size_(average_chunk_size) | |
| 56 | 7098261 | , maximal_chunk_size_(maximal_chunk_size) | |
| 57 | 49 | , threshold_( | |
| 58 | (average_chunk_size > 0) | ||
| 59 | 7098212 | ? (std::numeric_limits<uint32_t>::max() / average_chunk_size) | |
| 60 | : 0) | ||
| 61 | 7098261 | , xor32_ptr_(0) | |
| 62 |
2/2✓ Branch 1 taken 7098212 times.
✓ Branch 2 taken 49 times.
|
7098261 | , xor32_(0) { |
| 63 |
3/4✓ Branch 0 taken 7098212 times.
✓ Branch 1 taken 49 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 7098212 times.
|
7098261 | assert((average_chunk_size_ == 0) || (minimal_chunk_size_ > 0)); |
| 64 |
2/2✓ Branch 0 taken 7098212 times.
✓ Branch 1 taken 49 times.
|
7098261 | if (minimal_chunk_size_ > 0) { |
| 65 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 7098212 times.
|
7098212 | assert(minimal_chunk_size_ >= kXor32Window); |
| 66 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 7098212 times.
|
7098212 | assert(minimal_chunk_size_ < average_chunk_size_); |
| 67 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 7098212 times.
|
7098212 | assert(average_chunk_size_ < maximal_chunk_size_); |
| 68 | } | ||
| 69 | 7098261 | } | |
| 70 | |||
| 71 | |||
| 72 | 1578896 | uint64_t Xor32Detector::DoFindNextCutMark(BlockItem *buffer) { | |
| 73 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1578896 times.
|
1578896 | assert(minimal_chunk_size_ > 0); |
| 74 | 1578896 | 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 | 1578840 | const uint64_t global_offset = std::max( | |
| 81 | 1578840 | last_cut() + static_cast<uint64_t>(minimal_chunk_size_ - kXor32Window), | |
| 82 | 1578840 | xor32_ptr_); | |
| 83 | |||
| 84 | // Check if the next xor32 computation is taking place in the current buffer | ||
| 85 |
2/2✓ Branch 2 taken 627837 times.
✓ Branch 3 taken 951171 times.
|
1578812 | if (global_offset >= offset() + static_cast<uint64_t>(buffer->size())) { |
| 86 |
1/2✓ Branch 1 taken 627865 times.
✗ Branch 2 not taken.
|
627837 | return NoCut(global_offset); |
| 87 | } | ||
| 88 | |||
| 89 | // get the byte offset in the current buffer | ||
| 90 | 951171 | uint64_t internal_offset = global_offset - offset(); | |
| 91 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 951171 times.
|
951171 | 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 | 951171 | const uint64_t precompute_end = last_cut() + minimal_chunk_size_; | |
| 98 | 951199 | const int64_t internal_precompute_end = std::min( | |
| 99 | 951199 | static_cast<int64_t>(precompute_end - offset()), | |
| 100 | 951171 | static_cast<int64_t>(buffer->size())); | |
| 101 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 951143 times.
|
951143 | assert(internal_precompute_end - static_cast<int64_t>(internal_offset) |
| 102 | <= static_cast<int64_t>(kXor32Window)); | ||
| 103 |
2/2✓ Branch 0 taken 8666754 times.
✓ Branch 1 taken 951143 times.
|
9617897 | for (; static_cast<int64_t>(internal_offset) < internal_precompute_end; |
| 104 | ++internal_offset) { | ||
| 105 | 8666754 | 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 | 951143 | const uint64_t internal_max_chunk_size_end = last_cut() + maximal_chunk_size_ | |
| 112 | 951171 | - offset(); | |
| 113 | 951171 | const uint64_t internal_compute_end = std::min( | |
| 114 | 951171 | internal_max_chunk_size_end, static_cast<uint64_t>(buffer->size())); | |
| 115 |
2/2✓ Branch 0 taken 15220447177 times.
✓ Branch 1 taken 683760 times.
|
15221130937 | for (; internal_offset < internal_compute_end; ++internal_offset) { |
| 116 | 15220447177 | xor32(data[internal_offset]); | |
| 117 | |||
| 118 | // check if we found a cut mark | ||
| 119 |
2/2✓ Branch 1 taken 267523 times.
✓ Branch 2 taken 15199785098 times.
|
15190794365 | if (CheckThreshold()) { |
| 120 |
1/2✓ Branch 2 taken 267523 times.
✗ Branch 3 not taken.
|
267523 | 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 2926 times.
✓ Branch 1 taken 680834 times.
|
683760 | if (internal_offset == internal_max_chunk_size_end) { |
| 128 |
1/2✓ Branch 2 taken 2926 times.
✗ Branch 3 not taken.
|
2926 | return DoCut(internal_offset + offset()); |
| 129 | } else { | ||
| 130 |
1/2✓ Branch 2 taken 680806 times.
✗ Branch 3 not taken.
|
680834 | return NoCut(internal_offset + offset()); |
| 131 | } | ||
| 132 | } | ||
| 133 |