GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 30.1% 147 / 0 / 488
Functions: 37.3% 25 / 0 / 67
Branches: 11.9% 63 / 0 / 528
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 75530 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 392874 explicit SparseMaskIter(int mask) : mask_(mask) {}
34 392874 bool HasNext() const { return mask_ != 0; }
35 239196 unsigned Next() {
36 239196 unsigned i = __builtin_ctz(mask_);
37 239196 mask_ &= (mask_ - 1);
38 239196 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 392874 SparseMaskIter MatchTag(uint8_t tag) const {
53 392874 auto tag_vec = _mm_load_si128(static_cast<__m128i const*>( // NOLINT
54 392874 static_cast<const void*>(&tags_[0]))); // NOLINT
55 785748 auto cmp_val = _mm_set1_epi8(tag); // NOLINT
56 392874 auto eq_vec = _mm_cmpeq_epi8(tag_vec, cmp_val); // NOLINT
57 392874 auto mask = _mm_movemask_epi8(eq_vec) & kFullMask; // NOLINT
58 392874 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 75530 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 75530 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 75530 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
 75530 CHECK_LT(Size(), kMaxSize);
75 75530 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 75530 times.
✗ Branch 2 not taken.
 75530 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 75530 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 75530 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 75530 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 75530 times.
✗ Branch 4 not taken.
 75530 return Set(it.Next(), sign, ItemT{key, value});
79 }
80
81 75530 ItemT* Set(size_t i, uint8_t tag, const ItemT& val) {
82 75530 value_[i] = val;
83 ✗ IF_Persistence(clflushopt_range(&value_[i], sizeof(ItemT)););
84 75530 tags_[i] = tag;
85 75530 return value_ + i;
86 }
87 290084 ItemT* Get(size_t i) { return value_ + i; }
88 ✗ void IncOverflow() {
89 ✗ if (overflow_count_ != 255)
90 ✗ ++overflow_count_;
91 ✗ }
92 ✗ void DecOverflow() {
93 ✗ if (overflow_count_ != 255)
94 ✗ --overflow_count_;
95 ✗ }
96 ✗ void Delete(size_t i) {
97 ✗ tags_[i] = 0;
98 ✗ value_[i].first = -1;
99 ✗ IF_Persistence(
100 clflushopt_range(&value_[i].first, sizeof(value_[i].first)););
101 ✗ size_--;
102 ✗ }
103 78148 inline size_t OverflowCount() { return overflow_count_; }
104
105 151060 inline size_t Size() const { return size_; }
106 ✗ bool InUse(size_t i) const { return tags_[i] != 0; }
107 45613056 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 638582784 times.
✓ Branch 1 taken 45613056 times.
 684195840 for (int i = 0; i < kMaxSize; i++)
109 638582784 value_[i].first = -1;
110 45613056 }
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 348 PetHash() = default;
138
139 696 static int64_t OverFallChunkNum(uint64_t capacity) {
140 696 return Next2Power((capacity + kChunkSize - 1) / kChunkSize);
141 // return 2 * (capacity + kChunkSize - 1) / kChunkSize;
142 }
143
144 348 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 348 times.
✗ Branch 1 not taken.
 348 if (!ignore_load_factor)
146 348 capacity /= kMaxLoadFactor / 100.0;
147 348 chunk_num_ = OverFallChunkNum(capacity);
148 348 capacity_ = chunk_num_ * kChunkSize;
149 348 size_ = 0;
150 348 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 45613056 times.
✓ Branch 1 taken 348 times.
 45613404 for (uint64_t i = 0; i < chunk_num_; i++) {
152 45613056 chunk_table_[i].Initialize();
153 }
154 348 }
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 ✗ if (!ignore_load_factor)
163 ✗ capacity /= kMaxLoadFactor / 100.0;
164 // chunk_num_ = Next2Power((capacity + kChunkSize - 1) / kChunkSize);
165 ✗ 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 ✗ for (int i = 0; i < kRecoveryThread; ++i) {
173 ✗ uint64_t left = i * block_num;
174 ✗ uint64_t right = left + block_num;
175 ✗ thread_pool.push_back(std::thread([&, left, right] {
176 ✗ 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 ✗ for (int chunk_offset = 0; chunk_offset < ChunkT::kMaxSize;
183 chunk_offset++) {
184 ✗ 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 ✗ uint8 sign = Sign(hash_value);
192 ✗ if (UNLIKELY(chunk.tags_[chunk_offset] != sign)) {
193 // inconsistent tags
194 ✗ RECSTORE_LOG_EVERY_MS(WARNING, 2000)
195 ✗ << "inconsistent tag, key = " << chunkItem.first
196 ✗ << " , correct it";
197 ✗ chunk.tags_[chunk_offset] = sign;
198 }
199 }
200 }
201 }));
202 }
203 ✗ for (auto& each : thread_pool)
204 ✗ each.join();
205 ✗ size_.store(count_size);
206 ✗ if (fabs((double)old_size - (double)size_) >= 1000) {
207 ✗ LOG(ERROR) << "Large Diff after reload.";
208 }
209
210 // 设置 overflowbit
211 ✗ thread_pool.clear();
212 ✗ for (int i = 0; i < kRecoveryThread; ++i) {
213 ✗ uint64_t left = i * block_num;
214 ✗ uint64_t right = left + block_num;
215 ✗ thread_pool.push_back(std::thread([&, left, right] {
216 ✗ for (int chunk_id = left; chunk_id < right && chunk_id < chunk_num_;
217 chunk_id++) {
218 ✗ ChunkT& chunk = chunk_table_[chunk_id];
219 ✗ for (int chunk_offset = 0; chunk_offset < ChunkT::kMaxSize;
220 chunk_offset++) {
221 ✗ ItemT& chunkItem = chunk.value_[chunk_offset];
222 ✗ if (chunk.InUse(chunk_offset)) {
223 ✗ mallocSetValid(chunkItem.first, chunkItem.second);
224 ✗ uint64 hash_value = Hash(chunkItem.first);
225 ✗ size_t step = ProbeDelta(Sign(hash_value));
226 ✗ uint64 pos = hash_value & (chunk_num_ - 1);
227 ✗ 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 ✗ if (temp == 255)
240 ✗ break;
241 } while (
242 ✗ !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 ✗ for (auto& each : thread_pool)
252 ✗ each.join();
253 ✗ }
254
255 static uint64_t
256 348 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 348 times.
✗ Branch 1 not taken.
 348 if (!ignore_load_factor)
258 348 capacity /= kMaxLoadFactor / 100.0;
259 // auto chunk_table_num = Next2Power((capacity + kChunkSize - 1) /
260 // kChunkSize);
261 348 auto chunk_table_num = OverFallChunkNum(capacity);
262 348 return sizeof(PetHash) + chunk_table_num * sizeof(ChunkT);
263 }
264
265 696 static uint64_t Next2Power(uint64_t size) {
266 696 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 11832 times.
✓ Branch 1 taken 696 times.
 12528 while (new_size < size)
268 11832 new_size <<= 1;
269 696 return new_size;
270 }
271
272 ✗ bool Valid(int64_t memory_size) {
273 ✗ if (capacity_ == 0 && memory_size > 0) {
274 ✗ LOG(ERROR) << "PetHash invalid. capacity_ == 0";
275 ✗ return false;
276 }
277 ✗ if (size_ > capacity_) {
278 ✗ LOG(ERROR) << "PetHash invalid. dict size_ > capacity_";
279 ✗ return false;
280 }
281 ✗ if (chunk_num_ * kChunkSize != capacity_) {
282 ✗ LOG(ERROR) << "chunk_num_ * kChunkSize != capacity_";
283 ✗ return false;
284 }
285 ✗ if (memory_size != MemorySize(capacity_, true)) {
286 ✗ if (capacity_ != 0)
287 ✗ LOG(ERROR) << "PetHash invalid. memory_size != MemorySize(capacity_, "
288 "true), memory_size = "
289 ✗ << 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 ✗ for (uint64_t i = 0; i < capacity_; ++i) {
296 ✗ if (IndexInUse(i)) {
297 ✗ GetById(i, &key);
298 ✗ auto [value, exists] = Get(key);
299 ✗ if (!exists) {
300 ✗ LOG(ERROR) << "PetHash invalid. GetById has key, but Get(key) "
301 "failed; key is "
302 ✗ << key;
303 ✗ return false;
304 }
305 ✗ total_num++;
306 }
307 }
308 ✗ for (int i = 0; i < chunk_num_; ++i) {
309 ✗ chunk_table_total_num += chunk_table_[i].Size();
310 }
311 ✗ if (total_num != chunk_table_total_num)
312 ✗ LOG(ERROR) << fmt::format(
313 "PetHash invalid {} != {}", total_num, chunk_table_total_num);
314 ✗ if (total_num != size_)
315 ✗ LOG(ERROR) << fmt::format(
316 ✗ "PetHash invalid {} != {}", total_num, size_.load());
317 ✗ 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 103702 std::pair<const ValueT, bool> Get(const KeyT& key) const {
328 103702 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 103702 times.
✗ Branch 2 not taken.
 103702 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 103702 times.
✗ Branch 2 not taken.
 103702 return std::make_pair(value, exist);
332 }
333
334 ✗ std::pair<ValueT*, bool> GetReturnPtr(const KeyT& key) {
335 ✗ auto [value, p_value, exist] = GetInternal(key, nullptr, nullptr, nullptr);
336 ✗ return std::make_pair(p_value, exist);
337 }
338
339 22716 inline void HintPrefetch(const KeyT key) {
340 22716 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 22716 times.
✗ Branch 2 not taken.
 22716 auto sign = Sign(hash_value);
342 22716 size_t pos = hash_value & (chunk_num_ - 1);
343 22716 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 22716 times.
✗ Branch 2 not taken.
 22716 _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 22716 times.
✗ Branch 3 not taken.
 22716 _mm_prefetch((const char*)(chunk->Get(0)), _MM_HINT_T0);
346 22716 }
347
348 std::tuple<const ValueT, ValueT* const, bool>
349 103702 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 103702 RETRY:
354 103702 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 103702 times.
✗ Branch 2 not taken.
 103702 auto sign = Sign(hash_value);
356 103702 size_t step = ProbeDelta(sign);
357 103702 size_t pos = hash_value & (chunk_num_ - 1);
358 size_t id;
359 103702 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 103702 times.
✗ Branch 1 not taken.
 103702 for (size_t i = 0; i < chunk_num_; ++i) {
361 103702 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 103702 times.
✗ Branch 3 not taken.
 103702 _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 103702 times.
 103702 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 103702 times.
✗ Branch 2 not taken.
 103702 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 101088 times.
✓ Branch 2 taken 2614 times.
 103702 while (it.HasNext()) {
373 101088 id = it.Next();
374 101088 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 101088 times.
✗ Branch 1 not taken.
 101088 if (LIKELY(key == val->first)) {
377
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 101088 times.
 101088 if (item_pos != nullptr)
378 ✗ *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 101088 times.
 101088 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 101088 times.
 101088 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 101088 times.
✗ Branch 2 not taken.
 101088 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 2614 times.
✗ Branch 2 not taken.
 2614 if (LIKELY(chunk->OverflowCount() == 0))
387 2614 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 2614 times.
 2614 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 2614 times.
✗ Branch 2 not taken.
 2614 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 138108 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 138108 times.
 138108 if (old_value_out != nullptr) {
536 138108 *old_value_out = ValueT();
537 }
538
539 138108 RETRY:
540 138108 uint64_t hash_value = Hash(key);
541
1/2
✓ Branch 1 taken 138108 times.
✗ Branch 2 not taken.
 138108 auto sign = Sign(hash_value);
542 138108 size_t step = ProbeDelta(sign);
543 138108 size_t pos = hash_value & (chunk_num_ - 1);
544 138108 bool touch_migrating_chunk = false;
545
546
1/2
✓ Branch 0 taken 138108 times.
✗ Branch 1 not taken.
 138108 for (size_t i = 0; i < chunk_num_; ++i) {
547 138108 auto chunk = chunk_table_ + pos;
548
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 138108 times.
 138108 if (UNLIKELY(chunk->is_migrating)) {
549 ✗ touch_migrating_chunk = true;
550 }
551
552 {
553
1/2
✓ Branch 1 taken 138108 times.
✗ Branch 2 not taken.
 138108 auto it = chunk->MatchTag(sign);
554
2/2
✓ Branch 1 taken 62574 times.
✓ Branch 2 taken 75534 times.
 138108 while (it.HasNext()) {
555 62574 auto id = it.Next();
556 62574 auto val = chunk->Get(id);
557
1/2
✓ Branch 0 taken 62574 times.
✗ Branch 1 not taken.
 62574 if (LIKELY(key == val->first)) {
558
1/2
✓ Branch 0 taken 62574 times.
✗ Branch 1 not taken.
 62574 while (LIKELY(key == val->first)) {
559 62574 ValueT expected = val->second;
560 62574 ValueT desired = value;
561
1/2
✓ Branch 0 taken 62574 times.
✗ Branch 1 not taken.
 62574 if (__atomic_compare_exchange_n(&val->second,
562 &expected,
563 desired,
564 false,
565 __ATOMIC_ACQ_REL,
566 __ATOMIC_ACQUIRE)) {
567
1/2
✓ Branch 0 taken 62574 times.
✗ Branch 1 not taken.
 62574 if (old_value_out != nullptr) {
568 62574 *old_value_out = expected;
569 }
570 IF_Persistence(clflushopt_range(&val->second, sizeof(uint64)););
571 62574 return &val->second;
572 }
573 ✗ __asm__ volatile("pause" ::: "memory");
574 }
575 ✗ goto RETRY;
576 }
577 }
578 }
579
580
1/2
✓ Branch 1 taken 75534 times.
✗ Branch 2 not taken.
 75534 if (LIKELY(chunk->OverflowCount() == 0)) {
581 75534 break;
582 }
583 ✗ pos = (pos + step) & (chunk_num_ - 1);
584 }
585
586
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 75534 times.
 75534 if (UNLIKELY(touch_migrating_chunk)) {
587 ✗ goto RETRY;
588 }
589
2/4
✓ Branch 1 taken 75534 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 75534 times.
✗ Branch 5 not taken.
 75534 return Insert(key, value, check_func, is_force);
590 }
591
592 75534 std::pair<ChunkT*, size_t> HomeChunk(const KeyT& key) {
593 75534 uint64_t hash_value = Hash(key);
594 75534 size_t pos = hash_value & (chunk_num_ - 1);
595 75534 auto chunk = chunk_table_ + pos;
596
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 75534 times.
✗ Branch 2 not taken.
 151068 return std::make_pair(chunk, pos);
597 }
598
599 75534 ValueT* Insert(const KeyT& key,
600 const ValueT& value,
601 CheckFuncT check_func = nullptr,
602 bool force_insert = false) {
603 75534 uint64_t hash_value = Hash(key);
604
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 75534 times.
✗ Branch 2 not taken.
 75534 auto sign = Sign(hash_value);
605 75534 size_t step = ProbeDelta(sign);
606
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 75534 times.
✗ Branch 2 not taken.
 75534 auto [chunk, pos] = HomeChunk(key);
607
608
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 75534 times.
✓ Branch 3 taken 75534 times.
✗ Branch 4 not taken.
 151068 for (size_t i = 0; i < chunk_num_; ++i) {
609
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 75534 times.
✗ Branch 2 not taken.
 75534 base::AutoLock lock(chunk->lock_);
610 // check whether KV expire
611
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 75534 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 75534 times.
 75534 if (UNLIKELY(check_func && chunk->Size() >= kChunkSize - 2)) {
612 ✗ for (size_t id = 0; id < kChunkSize; ++id)
613 ✗ if (chunk->InUse(id)) {
614 ✗ auto it = chunk->Get(id);
615 ✗ if (!check_func(it->first, it->second, false))
616 ✗ Delete(it->first);
617 }
618 }
619
620 // re-search chunk
621 {
622
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 75534 times.
✗ Branch 2 not taken.
 75534 auto it = chunk->MatchTag(sign);
623
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 4 times.
✓ Branch 2 taken 75530 times.
 75534 while (it.HasNext()) {
624 4 auto id = it.Next();
625 4 auto val = chunk->Get(id);
626
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 4 times.
✗ Branch 1 not taken.
 4 if (LIKELY(key == val->first)) {
627 4 val->second = value;
628 4 return &val->second;
629 }
630 }
631 }
632
633
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 75530 times.
✗ Branch 2 not taken.
 75530 if (LIKELY(chunk->Size() < kChunkSize)) {
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 75530 times.
✗ Branch 2 not taken.
 75530 auto val = chunk->Insert(key, value, sign);
635 75530 size_++;
636 75530 return &val->second;
637 }
638 ✗ if (UNLIKELY(Full())) {
639 ✗ RECSTORE_LOG_EVERY_MS(ERROR, 1000) << fmt::format(
640 "Warning pethash dict full, {}/{}={}",
641 ✗ size_.load(),
642 ✗ capacity_,
643 ✗ size_ / (double)capacity_);
644 ✗ if (!force_insert) {
645 ✗ LOG(FATAL) << "dict OOM";
646 return nullptr;
647 }
648 ✗ auto it = chunk->Get((sign + i) % kChunkSize);
649 ✗ if (check_func != nullptr)
650 ✗ check_func(it->first, it->second, true);
651 ✗ Delete(it->first);
652 } else {
653 ✗ chunk->IncOverflow();
654 ✗ pos = (pos + step) & (chunk_num_ - 1);
655 ✗ chunk = chunk_table_ + pos;
656 }
657 }
658 ✗ LOG(FATAL) << "dict OOM";
659 return nullptr;
660 }
661 ✗ bool Delete(const KeyT& key) {
662 uint64_t pos;
663 ✗ auto [nouse0, nouse1, exists] = GetInternal(key, &pos);
664 ✗ if (!exists)
665 ✗ return true;
666
667 ✗ uint64_t hash_value = Hash(key);
668 ✗ size_t step = ProbeDelta(Sign(hash_value));
669 ✗ auto chunk_id = pos / kChunkSize;
670 ✗ auto chunk_offset = pos % kChunkSize;
671 ✗ pos = hash_value & (chunk_num_ - 1);
672 ✗ while (pos != chunk_id) {
673 ✗ chunk_table_[pos].DecOverflow();
674 ✗ pos = (pos + step) & (chunk_num_ - 1);
675 }
676 ✗ chunk_table_[chunk_id].Delete(chunk_offset);
677 ✗ size_--;
678 ✗ return true;
679 }
680
681 ✗ ValueT* GetById(uint64_t pos, KeyT* key = nullptr) {
682 ✗ auto it = chunk_table_[pos / kChunkSize].Get(pos % kChunkSize);
683 ✗ if (key != nullptr)
684 ✗ *key = it->first;
685 ✗ return &it->second;
686 }
687
688 ✗ bool IndexInUse(uint64_t pos) {
689 ✗ if (pos >= capacity_)
690 ✗ return false;
691 ✗ return chunk_table_[pos / kChunkSize].InUse(pos % kChunkSize);
692 }
693
694 int64_t Lookup(const KeyT& key) {
695 uint64_t pos;
696 auto [nouse0, nouse1, exists] = GetInternal(key, &pos);
697 if (exists)
698 return pos;
699 return -1;
700 }
701
702 ✗ uint32_t Size() { return size_; }
703
704 ✗ uint32_t Capacity() { return capacity_; }
705
706 ✗ inline bool Full() { return size_ * 100 >= capacity_ * kMaxLoadFactor; }
707
708 private:
709 317344 inline size_t ProbeDelta(size_t key) const { return key * 2 | 1; }
710
711 340060 static inline uint8_t Sign(const uint64_t& key) { // NOLINT
712 340060 uint64_t c = _mm_crc32_u64(0, key); // NOLINT
713 // ??????
714 // WARNING(xieminhui): diff from kuaishou
715 // key += c;
716 340060 return ((c >> 24) | 0x80) & kSignMask;
717 }
718
719 415594 static inline uint64_t Hash(uint64_t key) { return key * 0xc6a4a7935bd1e995; }
720
721 uint64_t capacity_;
722 uint64_t chunk_num_;
723 std::atomic<uint64_t> size_;
724 uint8_t not_use_[64 - 3 * sizeof(uint64_t)];
725 ChunkT chunk_table_[0];
726 };
727
728 } // namespace base
729