GCC Code Coverage Report

src/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
167 / 489
34.2%
Branches:
70 / 528
13.3%
Functions:
27 / 67
40.3%
storage/nvm/pet_kv/pet_hash.h
Line Branch Exec Source
1 #pragma once
2
3 #include <emmintrin.h> //NOLINT
4 #include <folly/GLog.h>
5 #include <nmmintrin.h> //NOLINT
6
7 #include <cmath>
8 #include <functional>
9 #include <iostream>
10 #include <thread>
11 #include <vector>
12
13 #include "base/array.h"
14 #include "base/base.h"
15 #include "persistence.h"
16
17 namespace base {
18
19 #pragma pack(push)
20 #pragma pack(2)
21 template <class K, class T>
22 struct EntryT {
23 EntryT() : first(), second() {}
24 76452 explicit EntryT(K s, T d) : first(s), second(d) {}
25 explicit EntryT(K s) : first(s), second() {}
26 K first;
27 T second;
28 };
29 #pragma pack(pop)
30
31 class SparseMaskIter {
32 public:
33 449102 explicit SparseMaskIter(int mask) : mask_(mask) {}
34 449102 bool HasNext() const { return mask_ != 0; }
35 293298 unsigned Next() {
36 293298 unsigned i = __builtin_ctz(mask_);
37 293298 mask_ &= (mask_ - 1);
38 293298 return i;
39 }
40 uint32_t Val() const { return mask_; }
41
42 private:
43 uint32_t mask_;
44 };
45
46 template <typename KeyT, typename ValueT, bool Persistence = false>
47 struct F14Chunk {
48 typedef EntryT<KeyT, ValueT> ItemT;
49 static constexpr int kMaxSize = 14;
50 static constexpr int kFullMask = (1 << kMaxSize) - 1;
51
52 449102 SparseMaskIter MatchTag(uint8_t tag) const {
53 449102 auto tag_vec = _mm_load_si128(static_cast<__m128i const*>( // NOLINT
54 449102 static_cast<const void*>(&tags_[0]))); // NOLINT
55 898204 auto cmp_val = _mm_set1_epi8(tag); // NOLINT
56 449102 auto eq_vec = _mm_cmpeq_epi8(tag_vec, cmp_val); // NOLINT
57 449102 auto mask = _mm_movemask_epi8(eq_vec) & kFullMask; // NOLINT
58 449102 return SparseMaskIter{mask};
59 }
60
61 int Find(const KeyT& key, uint8_t tag) {
62 auto it = MatchTag(tag);
63 while (it.HasNext()) {
64 auto id = it.Next();
65 auto pair = Get(id);
66 if (LIKELY(key == pair->first)) {
67 return id;
68 }
69 }
70 return -1;
71 }
72
73 76452 ItemT* Insert(const KeyT& key, const ValueT& value, const uint8_t sign) {
74
2/16
base::F14Chunk<unsigned long, base::PetKVData, true>::Insert(unsigned long const&, base::PetKVData const&, unsigned char):
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
base::F14Chunk<unsigned long, unsigned long, false>::Insert(unsigned long const&, unsigned long const&, unsigned char):
✓ Branch 4 taken 76452 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 76452 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
 76452 CHECK_LT(Size(), kMaxSize);
75 76452 size_++;
76
1/4
base::F14Chunk<unsigned long, base::PetKVData, true>::Insert(unsigned long const&, base::PetKVData const&, unsigned char):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::F14Chunk<unsigned long, unsigned long, false>::Insert(unsigned long const&, unsigned long const&, unsigned char):
✓ Branch 1 taken 76452 times.
✗ Branch 2 not taken.
 76452 auto it = MatchTag(0);
77
2/24
base::F14Chunk<unsigned long, base::PetKVData, true>::Insert(unsigned long const&, base::PetKVData const&, unsigned char):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
base::F14Chunk<unsigned long, unsigned long, false>::Insert(unsigned long const&, unsigned long const&, unsigned char):
✗ Branch 1 not taken.
✓ Branch 2 taken 76452 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 76452 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 76452 CHECK(it.HasNext());
78
1/4
base::F14Chunk<unsigned long, base::PetKVData, true>::Insert(unsigned long const&, base::PetKVData const&, unsigned char):
✗ Branch 3 not taken.
✗ Branch 4 not taken.
base::F14Chunk<unsigned long, unsigned long, false>::Insert(unsigned long const&, unsigned long const&, unsigned char):
✓ Branch 3 taken 76452 times.
✗ Branch 4 not taken.
 76452 return Set(it.Next(), sign, ItemT{key, value});
79 }
80
81 76452 ItemT* Set(size_t i, uint8_t tag, const ItemT& val) {
82 76452 value_[i] = val;
83 ✗ IF_Persistence(clflushopt_range(&value_[i], sizeof(ItemT)););
84 76452 tags_[i] = tag;
85 76452 return value_ + i;
86 }
87 345428 ItemT* Get(size_t i) { return value_ + i; }
88 ✗ void IncOverflow() {
89
0/4
base::F14Chunk<unsigned long, base::PetKVData, true>::IncOverflow():
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::F14Chunk<unsigned long, unsigned long, false>::IncOverflow():
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (overflow_count_ != 255)
90 ✗ ++overflow_count_;
91 ✗ }
92 ✗ void DecOverflow() {
93
0/4
base::F14Chunk<unsigned long, base::PetKVData, true>::DecOverflow():
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::F14Chunk<unsigned long, unsigned long, false>::DecOverflow():
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (overflow_count_ != 255)
94 ✗ --overflow_count_;
95 ✗ }
96 4 void Delete(size_t i) {
97 4 tags_[i] = 0;
98 4 value_[i].first = -1;
99 ✗ IF_Persistence(
100 clflushopt_range(&value_[i].first, sizeof(value_[i].first)););
101 4 size_--;
102 4 }
103 79352 inline size_t OverflowCount() { return overflow_count_; }
104
105 152904 inline size_t Size() const { return size_; }
106 ✗ bool InUse(size_t i) const { return tags_[i] != 0; }
107 47974208 void Initialize() {
108
2/4
base::F14Chunk<unsigned long, base::PetKVData, true>::Initialize():
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::F14Chunk<unsigned long, unsigned long, false>::Initialize():
✓ Branch 0 taken 671638912 times.
✓ Branch 1 taken 47974208 times.
 719613120 for (int i = 0; i < kMaxSize; i++)
109 671638912 value_[i].first = -1;
110 47974208 }
111
112 uint8_t tags_[kMaxSize];
113 uint8_t size_;
114 base::Lock lock_;
115 std::atomic<uint8_t> overflow_count_;
116 std::atomic<bool> is_migrating;
117 ItemT value_[kMaxSize];
118 } __attribute__((__aligned__(64)));
119
120 // The basic structure is borrowed from F14 hash in Folly
121 template <typename KeyT,
122 typename ValueT,
123 bool Persistence = false,
124 bool MM_PREFETCH = true>
125 class PetHash {
126 public:
127 typedef EntryT<KeyT, ValueT> ItemT;
128 typedef F14Chunk<KeyT, ValueT, Persistence> ChunkT;
129 typedef std::function<bool(
130 const KeyT&, const ValueT&, const bool& force_delete)>
131 CheckFuncT;
132 static constexpr size_t kChunkSize = ChunkT::kMaxSize;
133 static const uint32_t kSignBit = 8;
134 static const uint32_t kSignMask = (1 << kSignBit) - 1;
135 static const uint32_t kMaxLoadFactor = 90;
136
137 384 PetHash() = default;
138
139 768 static int64_t OverFallChunkNum(uint64_t capacity) {
140 768 return Next2Power((capacity + kChunkSize - 1) / kChunkSize);
141 // return 2 * (capacity + kChunkSize - 1) / kChunkSize;
142 }
143
144 384 void Initialize(uint64_t capacity, bool ignore_load_factor = false) {
145
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Initialize(unsigned long, bool):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Initialize(unsigned long, bool):
✓ Branch 0 taken 384 times.
✗ Branch 1 not taken.
 384 if (!ignore_load_factor)
146 384 capacity /= kMaxLoadFactor / 100.0;
147 384 chunk_num_ = OverFallChunkNum(capacity);
148 384 capacity_ = chunk_num_ * kChunkSize;
149 384 size_ = 0;
150 384 memset(chunk_table_, 0, chunk_num_ * sizeof(ChunkT));
151
2/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Initialize(unsigned long, bool):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Initialize(unsigned long, bool):
✓ Branch 0 taken 47974208 times.
✓ Branch 1 taken 384 times.
 47974592 for (uint64_t i = 0; i < chunk_num_; i++) {
152 47974208 chunk_table_[i].Initialize();
153 }
154 384 }
155
156 // Note(xieminhui) that mallocSetValid should be thread safe
157 ✗ void Reload(uint64_t capacity,
158 bool ignore_load_factor,
159 std::function<void(KeyT, ValueT)> mallocSetValid,
160 const int kRecoveryThread = 4) {
161 CHECK(Persistence) << "If not PMEM KV, dont use Reload";
162
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (!ignore_load_factor)
163 ✗ capacity /= kMaxLoadFactor / 100.0;
164 // chunk_num_ = Next2Power((capacity + kChunkSize - 1) / kChunkSize);
165
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ chunk_num_ = OverFallChunkNum(capacity);
166 ✗ capacity_ = chunk_num_ * kChunkSize;
167 ✗ uint64_t old_size = size_;
168 ✗ size_ = 0;
169 ✗ std::atomic<uint64_t> count_size(0);
170 ✗ std::vector<std::thread> thread_pool;
171 ✗ uint64_t block_num = chunk_num_ / kRecoveryThread + 1;
172
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ for (int i = 0; i < kRecoveryThread; ++i) {
173 ✗ uint64_t left = i * block_num;
174 ✗ uint64_t right = left + block_num;
175
0/4
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 ✗ thread_pool.push_back(std::thread([&, left, right] {
176
0/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 ✗ for (int chunk_id = left; chunk_id < right && chunk_id < chunk_num_;
177 chunk_id++) {
178 ✗ ChunkT& chunk = chunk_table_[chunk_id];
179 ✗ chunk.size_ = 0;
180 // reset inconsistent overflow_count_
181 ✗ chunk.overflow_count_ = 0;
182
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ for (int chunk_offset = 0; chunk_offset < ChunkT::kMaxSize;
183 chunk_offset++) {
184
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (chunk.value_[chunk_offset].first == -1)
185 ✗ continue;
186 ✗ chunk.size_++;
187 ✗ ItemT& chunkItem = chunk.value_[chunk_offset];
188 // 设置 size_ √
189 ✗ count_size++;
190 ✗ uint64 hash_value = Hash(chunkItem.first);
191
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ uint8 sign = Sign(hash_value);
192
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (UNLIKELY(chunk.tags_[chunk_offset] != sign)) {
193 // inconsistent tags
194
0/12
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
 ✗ RECSTORE_LOG_EVERY_MS(WARNING, 2000)
195
0/4
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 ✗ << "inconsistent tag, key = " << chunkItem.first
196
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ << " , correct it";
197 ✗ chunk.tags_[chunk_offset] = sign;
198 }
199 }
200 }
201 }));
202 }
203
0/2
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 ✗ for (auto& each : thread_pool)
204
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ each.join();
205 ✗ size_.store(count_size);
206
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (fabs((double)old_size - (double)size_) >= 1000) {
207
0/6
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ LOG(ERROR) << "Large Diff after reload.";
208 }
209
210 // 设置 overflowbit
211 ✗ thread_pool.clear();
212
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ for (int i = 0; i < kRecoveryThread; ++i) {
213 ✗ uint64_t left = i * block_num;
214 ✗ uint64_t right = left + block_num;
215
0/4
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 ✗ thread_pool.push_back(std::thread([&, left, right] {
216
0/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 ✗ for (int chunk_id = left; chunk_id < right && chunk_id < chunk_num_;
217 chunk_id++) {
218 ✗ ChunkT& chunk = chunk_table_[chunk_id];
219
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ for (int chunk_offset = 0; chunk_offset < ChunkT::kMaxSize;
220 chunk_offset++) {
221 ✗ ItemT& chunkItem = chunk.value_[chunk_offset];
222
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (chunk.InUse(chunk_offset)) {
223
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ mallocSetValid(chunkItem.first, chunkItem.second);
224 ✗ uint64 hash_value = Hash(chunkItem.first);
225
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ size_t step = ProbeDelta(Sign(hash_value));
226 ✗ uint64 pos = hash_value & (chunk_num_ - 1);
227
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ while (pos != chunk_id) {
228 /* before
229 * chunk_table_[pos].IncOverflow();
230 *********************************
231 * after
232 * overflow_count_ will only incr. Thus we
233 * can use CAS to do lock free while avoid overflow
234 */
235 ✗ uint8* prev_overflow_count = nullptr;
236 uint8_t temp;
237 do {
238 ✗ temp = chunk_table_[pos].overflow_count_;
239
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (temp == 255)
240 ✗ break;
241 } while (
242
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ !chunk_table_[pos].overflow_count_.compare_exchange_strong(
243 ✗ temp, temp + 1)); // NOLINT
244 ✗ pos = (pos + step) & (chunk_num_ - 1);
245 }
246 }
247 }
248 }
249 }));
250 }
251
0/2
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 ✗ for (auto& each : thread_pool)
252
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ each.join();
253 ✗ }
254
255 static uint64_t
256 384 MemorySize(uint64_t capacity, bool ignore_load_factor = false) {
257
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::MemorySize(unsigned long, bool):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::MemorySize(unsigned long, bool):
✓ Branch 0 taken 384 times.
✗ Branch 1 not taken.
 384 if (!ignore_load_factor)
258 384 capacity /= kMaxLoadFactor / 100.0;
259 // auto chunk_table_num = Next2Power((capacity + kChunkSize - 1) /
260 // kChunkSize);
261 384 auto chunk_table_num = OverFallChunkNum(capacity);
262 384 return sizeof(PetHash) + chunk_table_num * sizeof(ChunkT);
263 }
264
265 768 static uint64_t Next2Power(uint64_t size) {
266 768 uint64_t new_size = 1;
267
2/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Next2Power(unsigned long):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Next2Power(unsigned long):
✓ Branch 0 taken 12672 times.
✓ Branch 1 taken 768 times.
 13440 while (new_size < size)
268 12672 new_size <<= 1;
269 768 return new_size;
270 }
271
272 ✗ bool Valid(int64_t memory_size) {
273
0/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 ✗ if (capacity_ == 0 && memory_size > 0) {
274
0/6
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ LOG(ERROR) << "PetHash invalid. capacity_ == 0";
275 ✗ return false;
276 }
277
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (size_ > capacity_) {
278
0/6
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ LOG(ERROR) << "PetHash invalid. dict size_ > capacity_";
279 ✗ return false;
280 }
281
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (chunk_num_ * kChunkSize != capacity_) {
282
0/6
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ LOG(ERROR) << "chunk_num_ * kChunkSize != capacity_";
283 ✗ return false;
284 }
285
0/4
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 ✗ if (memory_size != MemorySize(capacity_, true)) {
286
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (capacity_ != 0)
287
0/6
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ LOG(ERROR) << "PetHash invalid. memory_size != MemorySize(capacity_, "
288 "true), memory_size = "
289
0/6
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ << memory_size << ", capacity_ = " << capacity_;
290 ✗ return false;
291 }
292 ✗ uint64_t total_num = 0;
293 ✗ uint64_t chunk_table_total_num = 0;
294 KeyT key;
295
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ for (uint64_t i = 0; i < capacity_; ++i) {
296
0/4
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 ✗ if (IndexInUse(i)) {
297 ✗ GetById(i, &key);
298
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ auto [value, exists] = Get(key);
299
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (!exists) {
300
0/6
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ LOG(ERROR) << "PetHash invalid. GetById has key, but Get(key) "
301 "failed; key is "
302
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ << key;
303 ✗ return false;
304 }
305 ✗ total_num++;
306 }
307 }
308
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ for (int i = 0; i < chunk_num_; ++i) {
309 ✗ chunk_table_total_num += chunk_table_[i].Size();
310 }
311
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (total_num != chunk_table_total_num)
312
0/8
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 ✗ LOG(ERROR) << fmt::format(
313 "PetHash invalid {} != {}", total_num, chunk_table_total_num);
314
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (total_num != size_)
315
0/6
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ LOG(ERROR) << fmt::format(
316
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 ✗ "PetHash invalid {} != {}", total_num, size_.load());
317
0/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 ✗ return total_num == chunk_table_total_num && total_num == size_;
318 }
319
320 void Debug() {
321 LOG(INFO) << "capacity_: " << capacity_;
322 LOG(INFO) << "chunk_num_: " << chunk_num_;
323 LOG(INFO) << "Chunk size: " << sizeof(ChunkT);
324 LOG(INFO) << "PetHash size: " << sizeof(PetHash);
325 }
326
327 105848 std::pair<const ValueT, bool> Get(const KeyT& key) const {
328 105848 auto* p = (PetHash<KeyT, ValueT, Persistence, MM_PREFETCH>*)(this);
329
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Get(unsigned long const&) const:
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Get(unsigned long const&) const:
✓ Branch 1 taken 105848 times.
✗ Branch 2 not taken.
 105848 auto [value, p_value, exist] =
330 p->GetInternal(key, nullptr, nullptr, nullptr);
331
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Get(unsigned long const&) const:
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Get(unsigned long const&) const:
✓ Branch 1 taken 105848 times.
✗ Branch 2 not taken.
 105848 return std::make_pair(value, exist);
332 }
333
334 ✗ std::pair<ValueT*, bool> GetReturnPtr(const KeyT& key) {
335
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ auto [value, p_value, exist] = GetInternal(key, nullptr, nullptr, nullptr);
336
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ return std::make_pair(p_value, exist);
337 }
338
339 22730 inline void HintPrefetch(const KeyT key) {
340 22730 uint64_t hash_value = Hash(key);
341
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::HintPrefetch(unsigned long):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::HintPrefetch(unsigned long):
✓ Branch 1 taken 22730 times.
✗ Branch 2 not taken.
 22730 auto sign = Sign(hash_value);
342 22730 size_t pos = hash_value & (chunk_num_ - 1);
343 22730 auto chunk = chunk_table_ + pos;
344
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::HintPrefetch(unsigned long):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::HintPrefetch(unsigned long):
✓ Branch 1 taken 22730 times.
✗ Branch 2 not taken.
 22730 _mm_prefetch((const char*)(chunk), _MM_HINT_T0);
345
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::HintPrefetch(unsigned long):
✗ Branch 2 not taken.
✗ Branch 3 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::HintPrefetch(unsigned long):
✓ Branch 2 taken 22730 times.
✗ Branch 3 not taken.
 22730 _mm_prefetch((const char*)(chunk->Get(0)), _MM_HINT_T0);
346 22730 }
347
348 std::tuple<const ValueT, ValueT* const, bool>
349 105852 GetInternal(const KeyT& key,
350 uint64* const item_pos = nullptr,
351 ChunkT** const chunk_pos = nullptr,
352 uint8_t* const in_chunk_id = nullptr) {
353 105852 RETRY:
354 105852 uint64_t hash_value = Hash(key);
355
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✓ Branch 1 taken 105852 times.
✗ Branch 2 not taken.
 105852 auto sign = Sign(hash_value);
356 105852 size_t step = ProbeDelta(sign);
357 105852 size_t pos = hash_value & (chunk_num_ - 1);
358 size_t id;
359 105852 bool touch_migrating_chunk = false;
360
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✓ Branch 0 taken 105852 times.
✗ Branch 1 not taken.
 105852 for (size_t i = 0; i < chunk_num_; ++i) {
361 105852 auto chunk = chunk_table_ + pos;
362 if (MM_PREFETCH) {
363
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 2 not taken.
✗ Branch 3 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✓ Branch 2 taken 105852 times.
✗ Branch 3 not taken.
 105852 _mm_prefetch(
364 static_cast<char const*>(static_cast<void const*>( // NOLINT
365 chunk->Get(3))),
366 _MM_HINT_T0); // NOLINT
367 }
368
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✗ Branch 1 not taken.
✓ Branch 2 taken 105852 times.
 105852 if (UNLIKELY(chunk->is_migrating))
369 ✗ touch_migrating_chunk = true;
370
371
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✓ Branch 1 taken 105852 times.
✗ Branch 2 not taken.
 105852 auto it = chunk->MatchTag(sign);
372
2/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✓ Branch 1 taken 102968 times.
✓ Branch 2 taken 2884 times.
 105852 while (it.HasNext()) {
373 102968 id = it.Next();
374 102968 auto val = chunk->Get(id);
375 // re-read the key to ensure no-one modify it
376
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✓ Branch 0 taken 102968 times.
✗ Branch 1 not taken.
 102968 if (LIKELY(key == val->first)) {
377
2/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 102964 times.
 102968 if (item_pos != nullptr)
378 4 *item_pos = pos * kChunkSize + id;
379
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✗ Branch 0 not taken.
✓ Branch 1 taken 102968 times.
 102968 if (chunk_pos != nullptr)
380 ✗ *chunk_pos = chunk;
381
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✗ Branch 0 not taken.
✓ Branch 1 taken 102968 times.
 102968 if (in_chunk_id != nullptr)
382 ✗ *in_chunk_id = id;
383
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✓ Branch 1 taken 102968 times.
✗ Branch 2 not taken.
 102968 return std::make_tuple(val->second, &val->second, true);
384 }
385 }
386
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✓ Branch 1 taken 2884 times.
✗ Branch 2 not taken.
 2884 if (LIKELY(chunk->OverflowCount() == 0))
387 2884 break;
388 ✗ pos = (pos + step) & (chunk_num_ - 1);
389 }
390
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✗ Branch 0 not taken.
✓ Branch 1 taken 2884 times.
 2884 if (UNLIKELY(touch_migrating_chunk))
391 ✗ goto RETRY;
392
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, base::PetKVData, true>**, unsigned char*):
✗ Branch 2 not taken.
✗ Branch 3 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::GetInternal(unsigned long const&, unsigned long*, base::F14Chunk<unsigned long, unsigned long, false>**, unsigned char*):
✓ Branch 1 taken 2884 times.
✗ Branch 2 not taken.
 2884 return std::make_tuple(ValueT(), nullptr, false);
393 }
394
395 ChunkT* const NextChunk(ChunkT* const chunk, const int step) {
396 auto p = chunk - chunk_table_;
397 p = (p + step + chunk_num_) % chunk_num_;
398 return chunk_table_ + p;
399 }
400 ChunkT* const PrevChunk(ChunkT* const chunk, const int step) {
401 auto p = chunk - chunk_table_;
402 p = (p - step + chunk_num_) % chunk_num_;
403 return chunk_table_ + p;
404 }
405
406 // start -> mid ... -> mid -> end , [start, end]
407 void ChainTraverseReverse(ChunkT* const start,
408 ChunkT* const end,
409 int step,
410 std::function<void(ChunkT* const)> func) {
411 ChunkT* current_chunk = end;
412 while (current_chunk != start) {
413 func(current_chunk);
414 current_chunk = PrevChunk(current_chunk, step);
415 }
416 func(current_chunk);
417 }
418
419 void ChainTraverse(ChunkT* const start,
420 ChunkT* const end,
421 int step,
422 std::function<void(ChunkT* const)> func) {
423 ChunkT* current_chunk = end;
424 while (current_chunk != start) {
425 func(current_chunk);
426 current_chunk = NextChunk(current_chunk, step);
427 }
428 func(current_chunk);
429 }
430
431 void HotnessAwareMigration(const base::ConstArray<KeyT> hot_keys) {
432 for (auto key : hot_keys) {
433 auto [home_chunk, home_chunk_id] = HomeChunk(key);
434 auto sign = Sign(Hash(key));
435 size_t hotkey_step = ProbeDelta(sign);
436 int id_in_chunk = home_chunk->Find(key, sign);
437 if (id_in_chunk != -1) {
438 // hot KV is already in its home chunk, continue
439 continue;
440 }
441 ChunkT* current_chunk;
442 uint8_t current_in_chunk_id;
443 auto [value, p_value_no_use, exists] =
444 GetInternal(key, nullptr, &current_chunk, &current_in_chunk_id);
445 CHECK(exists);
446
447 ChainTraverseReverse(
448 home_chunk, current_chunk, hotkey_step, [](ChunkT* const each) {
449 each->is_migrating = true;
450 });
451
452 // case 1: home_chunk has empty slot
453 if (LIKELY(home_chunk->Size() != kChunkSize)) {
454 // insert it to its home chunk
455 home_chunk->Insert(key, value, sign);
456 // remove it from its current chunk
457 current_chunk->Delete(current_in_chunk_id);
458 current_chunk->DecOverflow();
459 ChainTraverseReverse(
460 home_chunk,
461 current_chunk,
462 hotkey_step,
463 [current_chunk](ChunkT* const each) {
464 each->is_migrating = false;
465 });
466 continue;
467 }
468 // case 2: migration
469 // Step 2.1: home_chunk select a victim
470 KeyT victim_key = -1;
471 ValueT victim_value = -1;
472 int victim_id = 0;
473 CHECK(home_chunk->InUse(victim_id));
474 {
475 auto item = home_chunk->Get(victim_id);
476 victim_key = item->first;
477 victim_value = item->second;
478 }
479 // Step 2.2: insert a victim to another chunk
480 auto victim_sign = Sign(Hash(victim_key));
481 size_t victim_step = ProbeDelta(victim_sign);
482 size_t victim_pos = (home_chunk_id + victim_step) & (chunk_num_ - 1);
483 bool victim_migrated = false;
484 auto chunk = chunk_table_ + victim_pos;
485 for (size_t i = 0; i < chunk_num_; ++i) {
486 base::AutoLock lock(chunk->lock_);
487 if (LIKELY(chunk->Size() != kChunkSize)) {
488 chunk->Insert(victim_key, victim_value, victim_sign);
489 // 不能把victim又插回他原来的home_chunk
490 CHECK_NE(home_chunk, chunk);
491 victim_migrated = true;
492 break;
493 }
494 // 达到负载上限后需要删除才能插入
495 if (UNLIKELY(Full())) {
496 LOG(FATAL) << "todo: pet hash dict is full";
497 // let the insert thread first eviction
498 auto it = chunk->Get((sign + i) % kChunkSize);
499 Delete(it->first);
500 } else {
501 chunk->IncOverflow();
502 victim_pos = (victim_pos + victim_step) & (chunk_num_ - 1);
503 chunk = chunk_table_ + victim_pos;
504 }
505 }
506 CHECK(victim_migrated);
507 // Step 2.3: substitute victim with <key>
508 home_chunk->IncOverflow();
509 home_chunk->Set(victim_id, sign, ItemT{key, value});
510 current_chunk->Delete(current_in_chunk_id);
511 // all chunks along this chain should be reduced by 1
512 // (current_chunk, home_chunk]
513 ChainTraverseReverse(
514 home_chunk,
515 current_chunk,
516 hotkey_step,
517 [current_chunk](ChunkT* const each) {
518 // unlock
519 each->is_migrating = false;
520 // unlock done
521 if (each == current_chunk)
522 return;
523 each->DecOverflow();
524 });
525 }
526 }
527
528 190330 ValueT* Set(const KeyT& key,
529 const ValueT& value,
530 CheckFuncT check_func = nullptr,
531 bool is_force = false,
532 ValueT* old_value_out = nullptr) {
533 static_assert(sizeof(ValueT) <= sizeof(uint64_t),
534 "PetHash::Set CAS update expects a 64-bit-or-smaller value");
535
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 190330 times.
 190330 if (old_value_out != nullptr) {
536 190330 *old_value_out = ValueT();
537 }
538
539 190330 RETRY:
540 190330 uint64_t hash_value = Hash(key);
541
1/2
✓ Branch 1 taken 190330 times.
✗ Branch 2 not taken.
 190330 auto sign = Sign(hash_value);
542 190330 size_t step = ProbeDelta(sign);
543 190330 size_t pos = hash_value & (chunk_num_ - 1);
544 190330 bool touch_migrating_chunk = false;
545
546
1/2
✓ Branch 0 taken 190330 times.
✗ Branch 1 not taken.
 190330 for (size_t i = 0; i < chunk_num_; ++i) {
547 190330 auto chunk = chunk_table_ + pos;
548
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 190330 times.
 190330 if (UNLIKELY(chunk->is_migrating)) {
549 ✗ touch_migrating_chunk = true;
550 }
551
552 {
553
1/2
✓ Branch 1 taken 190330 times.
✗ Branch 2 not taken.
 190330 auto it = chunk->MatchTag(sign);
554
2/2
✓ Branch 1 taken 113862 times.
✓ Branch 2 taken 76468 times.
 190330 while (it.HasNext()) {
555 113862 auto id = it.Next();
556 113862 auto val = chunk->Get(id);
557
1/2
✓ Branch 0 taken 113862 times.
✗ Branch 1 not taken.
 113862 if (LIKELY(key == val->first)) {
558
1/2
✓ Branch 0 taken 113866 times.
✗ Branch 1 not taken.
 113866 while (LIKELY(key == val->first)) {
559 113866 ValueT expected = val->second;
560 113866 ValueT desired = value;
561 113866 if (__atomic_compare_exchange_n(
562
2/2
✓ Branch 0 taken 113862 times.
✓ Branch 1 taken 4 times.
 113866 &val->second,
563 &expected,
564 desired,
565 false,
566 __ATOMIC_ACQ_REL,
567 __ATOMIC_ACQUIRE)) {
568
1/2
✓ Branch 0 taken 113862 times.
✗ Branch 1 not taken.
 113862 if (old_value_out != nullptr) {
569 113862 *old_value_out = expected;
570 }
571 IF_Persistence(clflushopt_range(&val->second, sizeof(uint64)););
572 113862 return &val->second;
573 }
574 4 __asm__ volatile("pause" ::: "memory");
575 }
576 ✗ goto RETRY;
577 }
578 }
579 }
580
581
1/2
✓ Branch 1 taken 76468 times.
✗ Branch 2 not taken.
 76468 if (LIKELY(chunk->OverflowCount() == 0)) {
582 76468 break;
583 }
584 ✗ pos = (pos + step) & (chunk_num_ - 1);
585 }
586
587
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 76468 times.
 76468 if (UNLIKELY(touch_migrating_chunk)) {
588 ✗ goto RETRY;
589 }
590
2/4
✓ Branch 1 taken 76468 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 76468 times.
✗ Branch 5 not taken.
 76468 return Insert(key, value, check_func, is_force);
591 }
592
593 76468 std::pair<ChunkT*, size_t> HomeChunk(const KeyT& key) {
594 76468 uint64_t hash_value = Hash(key);
595 76468 size_t pos = hash_value & (chunk_num_ - 1);
596 76468 auto chunk = chunk_table_ + pos;
597
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::HomeChunk(unsigned long const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::HomeChunk(unsigned long const&):
✓ Branch 1 taken 76468 times.
✗ Branch 2 not taken.
 152936 return std::make_pair(chunk, pos);
598 }
599
600 76468 ValueT* Insert(const KeyT& key,
601 const ValueT& value,
602 CheckFuncT check_func = nullptr,
603 bool force_insert = false) {
604 76468 uint64_t hash_value = Hash(key);
605
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✓ Branch 1 taken 76468 times.
✗ Branch 2 not taken.
 76468 auto sign = Sign(hash_value);
606 76468 size_t step = ProbeDelta(sign);
607
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✓ Branch 1 taken 76468 times.
✗ Branch 2 not taken.
 76468 auto [chunk, pos] = HomeChunk(key);
608
609
2/8
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✓ Branch 2 taken 76468 times.
✓ Branch 3 taken 76468 times.
✗ Branch 4 not taken.
 152936 for (size_t i = 0; i < chunk_num_; ++i) {
610
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✓ Branch 1 taken 76468 times.
✗ Branch 2 not taken.
 76468 base::AutoLock lock(chunk->lock_);
611 // check whether KV expire
612
2/12
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✓ Branch 2 taken 76468 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 76468 times.
 76468 if (UNLIKELY(check_func && chunk->Size() >= kChunkSize - 2)) {
613
0/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ for (size_t id = 0; id < kChunkSize; ++id)
614
0/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (chunk->InUse(id)) {
615 ✗ auto it = chunk->Get(id);
616
0/8
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 ✗ if (!check_func(it->first, it->second, false))
617
0/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ Delete(it->first);
618 }
619 }
620
621 // re-search chunk
622 {
623
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✓ Branch 1 taken 76468 times.
✗ Branch 2 not taken.
 76468 auto it = chunk->MatchTag(sign);
624
2/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 76452 times.
 76468 while (it.HasNext()) {
625 16 auto id = it.Next();
626 16 auto val = chunk->Get(id);
627
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
 16 if (LIKELY(key == val->first)) {
628 16 val->second = value;
629 16 return &val->second;
630 }
631 }
632 }
633
634
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✓ Branch 1 taken 76452 times.
✗ Branch 2 not taken.
 76452 if (LIKELY(chunk->Size() < kChunkSize)) {
635
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✓ Branch 1 taken 76452 times.
✗ Branch 2 not taken.
 76452 auto val = chunk->Insert(key, value, sign);
636 76452 size_++;
637 76452 return &val->second;
638 }
639
0/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (UNLIKELY(Full())) {
640
0/28
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 ✗ RECSTORE_LOG_EVERY_MS(ERROR, 1000) << fmt::format(
641 "Warning pethash dict full, {}/{}={}",
642
0/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ size_.load(),
643 ✗ capacity_,
644 ✗ size_ / (double)capacity_);
645
0/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (!force_insert) {
646
0/12
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ LOG(FATAL) << "dict OOM";
647 return nullptr;
648 }
649 ✗ auto it = chunk->Get((sign + i) % kChunkSize);
650
0/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ if (check_func != nullptr)
651
0/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ check_func(it->first, it->second, true);
652
0/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ Delete(it->first);
653 } else {
654 ✗ chunk->IncOverflow();
655 ✗ pos = (pos + step) & (chunk_num_ - 1);
656 ✗ chunk = chunk_table_ + pos;
657 }
658 }
659
0/12
base::PetHash<unsigned long, base::PetKVData, true, true>::Insert(unsigned long const&, base::PetKVData const&, std::function<bool (unsigned long const&, base::PetKVData const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Insert(unsigned long const&, unsigned long const&, std::function<bool (unsigned long const&, unsigned long const&, bool const&)>, bool):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 ✗ LOG(FATAL) << "dict OOM";
660 return nullptr;
661 }
662 4 bool Delete(const KeyT& key) {
663 uint64_t pos;
664
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Delete(unsigned long const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Delete(unsigned long const&):
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 auto [nouse0, nouse1, exists] = GetInternal(key, &pos);
665
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Delete(unsigned long const&):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Delete(unsigned long const&):
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (!exists)
666 ✗ return true;
667
668 4 uint64_t hash_value = Hash(key);
669
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Delete(unsigned long const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Delete(unsigned long const&):
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 size_t step = ProbeDelta(Sign(hash_value));
670 4 auto chunk_id = pos / kChunkSize;
671 4 auto chunk_offset = pos % kChunkSize;
672 4 pos = hash_value & (chunk_num_ - 1);
673
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Delete(unsigned long const&):
✗ Branch 0 not taken.
✗ Branch 1 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Delete(unsigned long const&):
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 while (pos != chunk_id) {
674 ✗ chunk_table_[pos].DecOverflow();
675 ✗ pos = (pos + step) & (chunk_num_ - 1);
676 }
677
1/4
base::PetHash<unsigned long, base::PetKVData, true, true>::Delete(unsigned long const&):
✗ Branch 1 not taken.
✗ Branch 2 not taken.
base::PetHash<unsigned long, unsigned long, false, true>::Delete(unsigned long const&):
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 chunk_table_[chunk_id].Delete(chunk_offset);
678 4 size_--;
679 4 return true;
680 }
681
682 ✗ ValueT* GetById(uint64_t pos, KeyT* key = nullptr) {
683 ✗ auto it = chunk_table_[pos / kChunkSize].Get(pos % kChunkSize);
684
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (key != nullptr)
685 ✗ *key = it->first;
686 ✗ return &it->second;
687 }
688
689 ✗ bool IndexInUse(uint64_t pos) {
690
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (pos >= capacity_)
691 ✗ return false;
692 ✗ return chunk_table_[pos / kChunkSize].InUse(pos % kChunkSize);
693 }
694
695 int64_t Lookup(const KeyT& key) {
696 uint64_t pos;
697 auto [nouse0, nouse1, exists] = GetInternal(key, &pos);
698 if (exists)
699 return pos;
700 return -1;
701 }
702
703 ✗ uint32_t Size() { return size_; }
704
705 ✗ uint32_t Capacity() { return capacity_; }
706
707 ✗ inline bool Full() { return size_ * 100 >= capacity_ * kMaxLoadFactor; }
708
709 private:
710 372654 inline size_t ProbeDelta(size_t key) const { return key * 2 | 1; }
711
712 395384 static inline uint8_t Sign(const uint64_t& key) { // NOLINT
713 395384 uint64_t c = _mm_crc32_u64(0, key); // NOLINT
714 // ??????
715 // WARNING(xieminhui): diff from kuaishou
716 // key += c;
717 395384 return ((c >> 24) | 0x80) & kSignMask;
718 }
719
720 471852 static inline uint64_t Hash(uint64_t key) { return key * 0xc6a4a7935bd1e995; }
721
722 uint64_t capacity_;
723 uint64_t chunk_num_;
724 std::atomic<uint64_t> size_;
725 uint8_t not_use_[64 - 3 * sizeof(uint64_t)];
726 ChunkT chunk_table_[0];
727 };
728
729 } // namespace base
730