GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 70.0% 191 / 0 / 273
Functions: 76.0% 19 / 0 / 25
Branches: 52.4% 110 / 0 / 210
storage/index/dram/extendible_hash.cpp
Line Branch Exec Source
1 #include "extendible_hash.h"
2 #include "../utils/hash.h"
3 #include <cassert>
4 #include <cmath>
5 #include <iostream>
6 #include <thread>
7
8 size_t lockCount = 0;
9 size_t splitCount = 0;
10
11 94742 static inline uint64_t mypow(uint64_t x, unsigned int y) noexcept {
12
1/2
✓ Branch 0 taken 94742 times.
✗ Branch 1 not taken.
 94742 if (x == 2) {
13
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 94742 times.
 94742 if (y >= 64)
14 ✗ return std::numeric_limits<uint64_t>::max();
15 94742 return (1ULL << y);
16 }
17
18 ✗ if (x && ((x & (x - 1)) == 0)) {
19 ✗ unsigned k = __builtin_ctzll(x);
20 ✗ unsigned shift = k * 1u * y;
21 ✗ if (shift >= 64)
22 ✗ return std::numeric_limits<uint64_t>::max();
23 ✗ return (1ULL << shift);
24 }
25
26 ✗ uint64_t base = x, res = 1;
27 ✗ unsigned e = y;
28 ✗ while (e) {
29 ✗ if (e & 1)
30 ✗ res *= base;
31 ✗ e >>= 1;
32 ✗ if (e)
33 ✗ base *= base;
34 }
35 ✗ return res;
36 }
37
38 ✗ size_t Block::numElem(void) {
39 ✗ size_t sum = 0;
40 ✗ for (unsigned i = 0; i < kNumSlot; ++i) {
41 ✗ if (_[i].key != INVALID)
42 ✗ sum++;
43 }
44 ✗ return sum;
45 }
46
47 92732 int Block::Insert(
48 Key_t& key, Value_t value, size_t key_hash, Value_t* old_value) {
49 #ifdef INPLACE
50 if (sema == -1)
51 return -2;
52 # ifdef LSB
53 if ((key_hash & (size_t)mypow(2, local_depth) - 1) != pattern)
54 return -2;
55 # else
56 if ((key_hash >> (8 * sizeof(key_hash) - local_depth)) != pattern)
57 return -2;
58 # endif
59 auto lock = sema;
60 int ret = -1;
61 if (lock < 0)
62 return -2;
63 while (!CAS(&sema, &lock, lock + 1)) {
64 lock = sema;
65 if (lock < 0)
66 return -2;
67 }
68 Key_t LOCK = INVALID;
69 for (unsigned i = 0; i < kNumSlot; ++i) {
70 # ifdef LSB
71 if ((h(&_[i].key, sizeof(Key_t)) & (size_t)mypow(2, local_depth) - 1) !=
72 pattern) {
73 # else
74 if ((h(&_[i].key, sizeof(Key_t)) >> (8 * sizeof(key_hash) - local_depth)) !=
75 pattern) {
76 # endif
77 _[i].key = INVALID;
78 // auto invalid = _[slot].key;
79 // CAS(&_[slot].key, &invalid, INVALID);
80 // do I need clflush? i don't think so. as long as it is shared through
81 // cache..
82 }
83 if (CAS(&_[i].key, &LOCK, SENTINEL)) {
84 _[i].value = value;
85 mfence();
86 _[i].key = key;
87 ret = i;
88 break;
89 } else {
90 LOCK = INVALID;
91 }
92 }
93 lock = sema;
94 while (!CAS(&sema, &lock, lock - 1)) {
95 lock = sema;
96 }
97 return ret;
98 #else
99
2/2
✓ Branch 0 taken 2556 times.
✓ Branch 1 taken 90176 times.
 92732 if (sema == -1)
100 2556 return -2;
101 # ifdef LSB
102
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 90174 times.
 90176 if ((key_hash & (size_t)mypow(2, local_depth) - 1) != pattern)
103 2 return -2;
104 # else
105 if ((key_hash >> (8 * sizeof(key_hash) - local_depth)) != pattern)
106 return -2;
107 # endif
108 90174 auto lock = sema;
109
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 90174 times.
 90174 if (lock < 0)
110 ✗ return -2;
111 90174 int ret = -1;
112
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 90174 times.
 90230 while (!CAS(&sema, &lock, lock + 1)) {
113 56 lock = sema;
114
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 56 times.
 56 if (lock < 0)
115 ✗ return -2;
116 }
117
2/2
✓ Branch 0 taken 1141954 times.
✓ Branch 1 taken 58746 times.
 1200700 for (unsigned i = 0; i < kNumSlot; ++i) {
118
2/2
✓ Branch 0 taken 31428 times.
✓ Branch 1 taken 1110526 times.
 1141954 if (_[i].key == key) {
119 Value_t previous =
120 31428 __atomic_exchange_n(&_[i].value, value, __ATOMIC_ACQ_REL);
121
1/2
✓ Branch 0 taken 31428 times.
✗ Branch 1 not taken.
 31428 if (old_value != nullptr) {
122 31428 *old_value = previous;
123 }
124 31428 ret = i;
125 31428 lock = sema;
126
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 31428 times.
 31472 while (!CAS(&sema, &lock, lock - 1)) {
127 44 lock = sema;
128 }
129 31428 return ret;
130 }
131 }
132 58746 Key_t LOCK = INVALID;
133
2/2
✓ Branch 0 taken 693058 times.
✓ Branch 1 taken 4612 times.
 697670 for (unsigned i = 0; i < kNumSlot; ++i) {
134
2/2
✓ Branch 0 taken 54134 times.
✓ Branch 1 taken 638924 times.
 693058 if (CAS(&_[i].key, &LOCK, SENTINEL)) {
135 54134 _[i].value = value;
136 54134 mfence();
137 54134 _[i].key = key;
138 54134 ret = i;
139 54134 break;
140 } else {
141 638924 LOCK = INVALID;
142 }
143 }
144 58746 lock = sema;
145
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 58746 times.
 58752 while (!CAS(&sema, &lock, lock - 1)) {
146 6 lock = sema;
147 }
148 58746 return ret;
149 #endif
150 }
151
152 73056 void Block::Insert4split(Key_t& key, Value_t value) {
153
1/2
✓ Branch 0 taken 344244 times.
✗ Branch 1 not taken.
 344244 for (unsigned i = 0; i < kNumSlot; ++i) {
154
2/2
✓ Branch 0 taken 73056 times.
✓ Branch 1 taken 271188 times.
 344244 if (_[i].key == INVALID) {
155 73056 _[i].key = key;
156 73056 _[i].value = value;
157 73056 return;
158 }
159 }
160 }
161
162 4612 Block** Block::Split(void) {
163 using namespace std;
164 4612 int64_t lock = 0;
165
2/2
✓ Branch 0 taken 46 times.
✓ Branch 1 taken 4566 times.
 4612 if (!CAS(&sema, &lock, -1))
166 46 return nullptr;
167
168 #ifdef INPLACE
169 Block** split = new Block*[2];
170 split[0] = this;
171 split[1] = new Block(local_depth + 1);
172
173 for (unsigned i = 0; i < kNumSlot; ++i) {
174 auto key_hash = h(&_[i].key, sizeof(Key_t));
175 # ifdef LSB
176 if (key_hash & ((size_t)1 << local_depth)) {
177 # else
178 if (key_hash & ((size_t)1 << ((sizeof(Key_t) * 8 - local_depth - 1)))) {
179 # endif
180 split[1]->Insert4split(_[i].key, _[i].value);
181 }
182 }
183
184 clflush((char*)split[1], sizeof(Block));
185 local_depth = local_depth + 1;
186 clflush((char*)&local_depth, sizeof(size_t));
187
188 return split;
189 #else
190
1/2
✓ Branch 1 taken 4566 times.
✗ Branch 2 not taken.
 4566 Block** split = new Block*[2];
191
1/2
✓ Branch 1 taken 4566 times.
✗ Branch 2 not taken.
 4566 split[0] = new Block(local_depth + 1);
192
1/2
✓ Branch 1 taken 4566 times.
✗ Branch 2 not taken.
 4566 split[1] = new Block(local_depth + 1);
193
194
2/2
✓ Branch 0 taken 73056 times.
✓ Branch 1 taken 4566 times.
 77622 for (unsigned i = 0; i < kNumSlot; ++i) {
195
1/2
✓ Branch 1 taken 73056 times.
✗ Branch 2 not taken.
 73056 auto key_hash = h(&_[i].key, sizeof(Key_t));
196 # ifdef LSB
197
2/2
✓ Branch 0 taken 35988 times.
✓ Branch 1 taken 37068 times.
 73056 if (key_hash & ((size_t)1 << (local_depth))) {
198 # else
199 if (key_hash & ((size_t)1 << ((sizeof(Key_t) * 8 - local_depth - 1)))) {
200 # endif
201
1/2
✓ Branch 1 taken 35988 times.
✗ Branch 2 not taken.
 35988 split[1]->Insert4split(_[i].key, _[i].value);
202 } else {
203
1/2
✓ Branch 1 taken 37068 times.
✗ Branch 2 not taken.
 37068 split[0]->Insert4split(_[i].key, _[i].value);
204 }
205 }
206
207 4566 clflush((char*)split[0], sizeof(Block));
208 4566 clflush((char*)split[1], sizeof(Block));
209
210 4566 return split;
211 #endif
212 }
213
214 ✗ bool Block::Delete(Key_t& key) {
215 ✗ if (sema == -1)
216 ✗ return false;
217
218 ✗ int64_t lock = sema;
219 ✗ if (lock < 0)
220 ✗ return false;
221 ✗ while (!CAS(&sema, &lock, lock + 1)) {
222 ✗ lock = sema;
223 ✗ if (lock < 0)
224 ✗ return false;
225 }
226
227 ✗ bool found = false;
228 ✗ for (unsigned i = 0; i < kNumSlot; ++i) {
229 ✗ if (_[i].key == key) {
230 ✗ _[i].key = INVALID;
231 ✗ clflush((char*)&_[i].key, sizeof(Key_t));
232 ✗ found = true;
233 ✗ break;
234 }
235 }
236
237 ✗ lock = sema;
238 ✗ while (!CAS(&sema, &lock, lock - 1)) {
239 ✗ lock = sema;
240 }
241 ✗ return found;
242 }
243
244 382 ExtendibleHash::ExtendibleHash(const BaseKVConfig& config)
245 : Index(config),
246
1/2
✓ Branch 1 taken 382 times.
✗ Branch 2 not taken.
 382 dir{[&config]() -> size_t {
247
2/2
✓ Branch 1 taken 352 times.
✓ Branch 2 taken 30 times.
 382 if (!config.json_config_.contains("initial_capacity")) {
248
2/4
✓ Branch 2 taken 352 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 352 times.
✗ Branch 6 not taken.
 352 LOG(WARNING) << "ExtendibleHash config missing 'initial_capacity'";
249 352 return 1;
250 }
251 const size_t init_cap =
252 30 config.json_config_.at("initial_capacity").get<size_t>();
253
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 30 times.
 30 if (init_cap == 0) {
254 ✗ LOG(WARNING)
255 ✗ << "ExtendibleHash config has invalid 'initial_capacity'=0";
256 ✗ return 1;
257 }
258 30 return init_cap;
259 }()},
260
1/2
✓ Branch 2 taken 382 times.
✗ Branch 3 not taken.
 382 global_depth{0} {
261 // Customize based on config, e.g.
262
3/6
✓ Branch 1 taken 382 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 382 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 382 times.
✗ Branch 8 not taken.
 382 LOG(INFO) << "DRAM index init";
263 382 global_depth = static_cast<size_t>(log2(dir.capacity));
264
2/2
✓ Branch 0 taken 832 times.
✓ Branch 1 taken 382 times.
 1214 for (unsigned i = 0; i < dir.capacity; ++i) {
265
1/2
✓ Branch 1 taken 832 times.
✗ Branch 2 not taken.
 832 dir._[i] = new Block(global_depth);
266 832 dir._[i]->pattern = i;
267 }
268 382 }
269
270 764 ExtendibleHash::~ExtendibleHash() {}
271
272 7060 void Directory::LSBUpdate(
273 int local_depth, int global_depth, int dir_cap, int x, Block** s) {
274 7060 int depth_diff = global_depth - local_depth;
275
2/2
✓ Branch 0 taken 5570 times.
✓ Branch 1 taken 1490 times.
 7060 if (depth_diff == 0) {
276
2/2
✓ Branch 0 taken 2430 times.
✓ Branch 1 taken 3140 times.
 5570 if ((x % dir_cap) >= dir_cap / 2) {
277 2430 _[x - dir_cap / 2] = s[0];
278 2430 clflush((char*)&_[x - dir_cap / 2], sizeof(Block*));
279 2430 _[x] = s[1];
280 2430 clflush((char*)&_[x], sizeof(Block*));
281 } else {
282 3140 _[x] = s[0];
283 3140 clflush((char*)&_[x], sizeof(Block*));
284 3140 _[x + dir_cap / 2] = s[1];
285 3140 clflush((char*)&_[x + dir_cap / 2], sizeof(Block*));
286 }
287 } else {
288
2/2
✓ Branch 0 taken 766 times.
✓ Branch 1 taken 724 times.
 1490 if ((x % dir_cap) >= dir_cap / 2) {
289 766 LSBUpdate(local_depth + 1, global_depth, dir_cap / 2, x - dir_cap / 2, s);
290 766 LSBUpdate(local_depth + 1, global_depth, dir_cap / 2, x, s);
291 } else {
292 724 LSBUpdate(local_depth + 1, global_depth, dir_cap / 2, x, s);
293 724 LSBUpdate(local_depth + 1, global_depth, dir_cap / 2, x + dir_cap / 2, s);
294 }
295 }
296 7060 return;
297 }
298
299 85562 Value_t ExtendibleHash::Insert(Key_t& key, Value_t value) {
300 using namespace std;
301
1/2
✓ Branch 1 taken 85562 times.
✗ Branch 2 not taken.
 85562 auto key_hash = h(&key, sizeof(key));
302 85562 Value_t old_value = kValueHandleNone;
303
304 92732 RETRY:
305 #ifdef LSB
306 // auto x = (key_hash & (pow(2, global_depth)-1));
307 92732 auto x = (key_hash % dir.capacity);
308 #else
309 auto x = (key_hash >> (8 * sizeof(key_hash) - global_depth));
310 #endif
311 92732 auto target = dir._[x];
312
1/2
✓ Branch 1 taken 92732 times.
✗ Branch 2 not taken.
 92732 auto ret = target->Insert(key, value, key_hash, &old_value);
313
314
2/2
✓ Branch 0 taken 4612 times.
✓ Branch 1 taken 88120 times.
 92732 if (ret == -1) {
315
1/2
✓ Branch 1 taken 4612 times.
✗ Branch 2 not taken.
 4612 Block** s = target->Split();
316
2/2
✓ Branch 0 taken 46 times.
✓ Branch 1 taken 4566 times.
 4612 if (s == nullptr) {
317 // another thread is doing split
318 46 goto RETRY;
319 }
320
321 #ifdef LSB
322 4566 s[0]->pattern = (key_hash % (size_t)mypow(2, s[0]->local_depth - 1));
323 4566 s[1]->pattern = s[0]->pattern + (1 << (s[0]->local_depth - 1));
324 #else
325 s[0]->pattern =
326 (key_hash >> (8 * sizeof(key_hash) - s[0]->local_depth + 1)) << 1;
327 s[1]->pattern =
328 ((key_hash >> (8 * sizeof(key_hash) - s[1]->local_depth + 1)) << 1) + 1;
329 #endif
330
331 // Directory management
332
2/2
✓ Branch 1 taken 7586 times.
✓ Branch 2 taken 4566 times.
 12152 while (!dir.Acquire()) {
333 // lockCount ++;
334 }
335 // dir.sema++;
336 { // CRITICAL SECTION - directory update
337 // auto prev = x;
338 #ifdef LSB
339 4566 x = (key_hash % dir.capacity);
340 #else
341 x = (key_hash >> (8 * sizeof(key_hash) - global_depth));
342 #endif
343 #ifdef INPLACE
344 if (dir._[x]->local_depth - 1 < global_depth) { // normal split
345 #else
346
2/2
✓ Branch 0 taken 4080 times.
✓ Branch 1 taken 486 times.
 4566 if (dir._[x]->local_depth < global_depth) { // normal split
347 #endif
348 #ifdef LSB
349
1/2
✓ Branch 1 taken 4080 times.
✗ Branch 2 not taken.
 4080 dir.LSBUpdate(s[0]->local_depth, global_depth, dir.capacity, x, s);
350 #else
351 unsigned depth_diff = global_depth - s[0]->local_depth;
352 if (depth_diff == 0) {
353 if (x % 2 == 0) {
354 dir._[x + 1] = s[1];
355 # ifdef INPLACE
356 clflush((char*)&dir._[x + 1], 8);
357 # else
358 mfence();
359 dir._[x] = s[0];
360 clflush((char*)&dir._[x], 16);
361 # endif
362 } else {
363 dir._[x] = s[1];
364 # ifdef INPLACE
365 clflush((char*)&dir._[x], 8);
366 # else
367 mfence();
368 dir._[x - 1] = s[0];
369 clflush((char*)&dir._[x - 1], 16);
370 # endif
371 }
372 } else {
373 int chunk_size = mypow(2, global_depth - (s[0]->local_depth - 1));
374 x = x - (x % chunk_size);
375 for (unsigned i = 0; i < chunk_size / 2; ++i) {
376 dir._[x + chunk_size / 2 + i] = s[1];
377 }
378 clflush((char*)&dir._[x + chunk_size / 2],
379 sizeof(void*) * chunk_size / 2);
380 # ifndef INPLACE
381 for (unsigned i = 0; i < chunk_size / 2; ++i) {
382 dir._[x + i] = s[0];
383 }
384 clflush((char*)&dir._[x], sizeof(void*) * chunk_size / 2);
385 # endif
386 }
387 #endif
388 } else { // directory doubling
389 486 auto d = dir._;
390
2/4
✓ Branch 0 taken 486 times.
✗ Branch 1 not taken.
✓ Branch 4 taken 486 times.
✗ Branch 5 not taken.
 486 auto _dir = new Block*[dir.capacity * 2];
391 #ifdef LSB
392 486 memcpy(_dir, d, sizeof(Block*) * dir.capacity);
393 486 memcpy(_dir + dir.capacity, d, sizeof(Block*) * dir.capacity);
394 486 _dir[x] = s[0];
395 486 _dir[x + dir.capacity] = s[1];
396 #else
397 for (unsigned i = 0; i < dir.capacity; ++i) {
398 if (i == x) {
399 _dir[2 * i] = s[0];
400 _dir[2 * i + 1] = s[1];
401 } else {
402 _dir[2 * i] = d[i];
403 _dir[2 * i + 1] = d[i];
404 }
405 }
406 #endif
407 486 clflush((char*)&dir._[0], sizeof(Block*) * dir.capacity);
408 486 dir._ = _dir;
409 486 clflush((char*)&dir._, sizeof(void*));
410 486 dir.capacity *= 2;
411 486 clflush((char*)&dir.capacity, sizeof(size_t));
412 486 global_depth += 1;
413 486 clflush((char*)&global_depth, sizeof(global_depth));
414
1/2
✓ Branch 0 taken 486 times.
✗ Branch 1 not taken.
 486 delete[] d;
415 // TODO: requiered to do this atomically
416 // cout << x << " directory doubling " << target << " " << dir._[x]<<
417 // endl;
418 }
419 #ifdef INPLACE
420 s[0]->sema = 0;
421 #endif
422 } // End of critical section
423 // dir.sema--;
424
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 4566 times.
 4566 while (!dir.Release()) {
425 // lockCount ++;
426 }
427 4566 goto RETRY;
428
2/2
✓ Branch 0 taken 2558 times.
✓ Branch 1 taken 85562 times.
 88120 } else if (ret == -2) {
429 // Block is splitting or directory pointers are stale; retry without
430 // recursion.
431
2/2
✓ Branch 0 taken 2556 times.
✓ Branch 1 taken 2 times.
 2558 if (target->sema == -1) {
432 2556 std::this_thread::yield();
433 }
434 2558 goto RETRY;
435 } else {
436 85562 clflush((char*)&dir._[x]->_[ret], sizeof(Pair));
437 }
438 85562 return old_value;
439 }
440
441 // This function does not allow resizing
442 ✗ bool ExtendibleHash::InsertOnly(Key_t& key, Value_t value) {
443 ✗ auto key_hash = h(&key, sizeof(key));
444 #ifdef LSB
445 ✗ auto x = (key_hash % dir.capacity);
446 #else
447 auto x = (key_hash >> (8 * sizeof(key_hash) - global_depth));
448 #endif
449
450 ✗ auto ret = dir._[x]->Insert(key, value, key_hash);
451 ✗ if (ret > -1) {
452 ✗ clflush((char*)&dir._[x]->_[ret], sizeof(Pair));
453 ✗ return true;
454 }
455
456 ✗ return false;
457 }
458
459 ✗ bool ExtendibleHash::Delete(Key_t& key) {
460 ✗ auto key_hash = h(&key, sizeof(key));
461 #ifdef LSB
462 ✗ auto x = (key_hash % dir.capacity);
463 #else
464 auto x = (key_hash >> (8 * sizeof(key_hash) - global_depth));
465 #endif
466
467 ✗ Block* target = dir._[x];
468 ✗ bool success = target->Delete(key);
469
470 ✗ if (!success && target->sema == -1) {
471 ✗ std::this_thread::yield();
472 ✗ x = (key_hash % dir.capacity);
473 ✗ success = dir._[x]->Delete(key);
474 }
475 ✗ return success;
476 }
477
478 85918 size_t ExtendibleHash::DirectoryIndex(size_t key_hash) const {
479 #ifdef LSB
480 85918 return key_hash % dir.capacity;
481 #else
482 return key_hash >> (8 * sizeof(key_hash) - global_depth);
483 #endif
484 }
485
486 66332 Value_t ExtendibleHash::ExtractWithHash(Key_t& key, size_t key_hash) {
487 66332 auto x = DirectoryIndex(key_hash);
488
489 66332 auto dir_ = dir._[x];
490
491 #ifdef INPLACE
492 auto sema = dir._[x]->sema;
493 while (!CAS(&dir._[x]->sema, &sema, sema + 1)) {
494 sema = dir._[x]->sema;
495 }
496 #endif
497
498
2/2
✓ Branch 0 taken 431576 times.
✓ Branch 1 taken 1308 times.
 432884 for (unsigned i = 0; i < Block::kNumSlot; ++i) {
499
2/2
✓ Branch 0 taken 65024 times.
✓ Branch 1 taken 366552 times.
 431576 if (dir_->_[i].key == key) {
500 #ifdef INPLACE
501 sema = dir._[x]->sema;
502 while (!CAS(&dir._[x]->sema, &sema, sema - 1)) {
503 sema = dir._[x]->sema;
504 }
505 #endif
506 65024 return dir_->_[i].value;
507 }
508 366552 lockCount++;
509 }
510
511 #ifdef INPLACE
512 sema = dir._[x]->sema;
513 while (!CAS(&dir._[x]->sema, &sema, sema - 1)) {
514 sema = dir._[x]->sema;
515 }
516 #endif
517 1308 return NONE;
518 }
519
520 45224 Value_t ExtendibleHash::Extract(Key_t& key) {
521 45224 auto key_hash = h(&key, sizeof(key));
522 45224 return ExtractWithHash(key, key_hash);
523 }
524
525 // Debugging function
526 ✗ Value_t ExtendibleHash::FindAnyway(Key_t& key) {
527 using namespace std;
528 ✗ for (size_t i = 0; i < dir.capacity; ++i) {
529 ✗ for (size_t j = 0; j < Block::kNumSlot; ++j) {
530 ✗ if (dir._[i]->_[j].key == key) {
531 ✗ auto key_hash = h(&key, sizeof(key));
532 ✗ auto x = (key_hash >> (8 * sizeof(key_hash) - global_depth));
533 ✗ return dir._[i]->_[j].value;
534 }
535 }
536 }
537 ✗ return NONE;
538 }
539
540 // Not accurate
541 4 double ExtendibleHash::Utilization(void) {
542 4 size_t sum = 0;
543 4 std::unordered_map<Block*, bool> set;
544
2/2
✓ Branch 0 taken 288 times.
✓ Branch 1 taken 4 times.
 292 for (size_t i = 0; i < dir.capacity; ++i) {
545
1/2
✓ Branch 1 taken 288 times.
✗ Branch 2 not taken.
 288 set[dir._[i]] = true;
546 }
547
2/2
✓ Branch 5 taken 210 times.
✓ Branch 6 taken 4 times.
 214 for (auto& elem : set) {
548
2/2
✓ Branch 0 taken 3360 times.
✓ Branch 1 taken 210 times.
 3570 for (unsigned i = 0; i < Block::kNumSlot; ++i) {
549
2/2
✓ Branch 0 taken 2020 times.
✓ Branch 1 taken 1340 times.
 3360 if (elem.first->_[i].key != INVALID)
550 2020 sum++;
551 }
552 }
553 8 return ((double)sum) / ((double)set.size() * Block::kNumSlot) * 100.0;
554 4 }
555
556 ✗ void Directory::SanityCheck(void* addr) {
557 using namespace std;
558 ✗ for (unsigned i = 0; i < capacity; ++i) {
559 ✗ if (_[i] == addr) {
560 ✗ cout << i << " " << _[i]->sema << endl;
561 ✗ exit(1);
562 }
563 }
564 ✗ }
565
566 6 size_t ExtendibleHash::Capacity(void) {
567 6 std::unordered_map<Block*, bool> set;
568
2/2
✓ Branch 0 taken 320 times.
✓ Branch 1 taken 6 times.
 326 for (size_t i = 0; i < dir.capacity; ++i) {
569
1/2
✓ Branch 1 taken 320 times.
✗ Branch 2 not taken.
 320 set[dir._[i]] = true;
570 }
571 12 return set.size() * Block::kNumSlot;
572 6 }
573
574 45224 void ExtendibleHash::Get(Key_t key, Value_t& pointer, unsigned tid) {
575 45224 pointer = Extract(key);
576 45224 }
577
578 85562 Value_t ExtendibleHash::Put(Key_t key, Value_t pointer, unsigned tid) {
579 85562 return Insert(key, static_cast<Value_t>(pointer));
580 }
581
582 19586 void ExtendibleHash::HintPrefetch(size_t key_hash) const {
583 19586 const auto x = DirectoryIndex(key_hash);
584 19586 __builtin_prefetch(dir._ + x, 0, 1);
585 19586 Block* block = dir._[x];
586
1/2
✓ Branch 0 taken 19586 times.
✗ Branch 1 not taken.
 19586 if (block != nullptr) {
587 19586 __builtin_prefetch(block, 0, 1);
588 }
589 19586 }
590
591 424 void ExtendibleHash::BatchGet(
592 base::ConstArray<Key_t> keys, Value_t* pointers, unsigned tid) {
593
3/6
✓ Branch 0 taken 424 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 424 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 424 times.
 424 if (pointers == nullptr || keys.Size() == 0) {
594 ✗ LOG(FATAL) << "Invalid pointers array or empty keys";
595 }
596 424 constexpr size_t kPrefetchDistance = 4;
597
2/2
✓ Branch 1 taken 21108 times.
✓ Branch 2 taken 424 times.
 21532 for (size_t i = 0; i < keys.Size(); ++i) {
598 21108 Key_t key = keys[static_cast<int>(i)];
599
1/2
✓ Branch 1 taken 21108 times.
✗ Branch 2 not taken.
 21108 auto key_hash = h(&key, sizeof(key));
600
2/2
✓ Branch 1 taken 19586 times.
✓ Branch 2 taken 1522 times.
 21108 if (i + kPrefetchDistance < static_cast<size_t>(keys.Size())) {
601 19586 Key_t prefetch_key = keys[static_cast<int>(i + kPrefetchDistance)];
602
2/4
✓ Branch 1 taken 19586 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 19586 times.
✗ Branch 5 not taken.
 19586 HintPrefetch(h(&prefetch_key, sizeof(prefetch_key)));
603 }
604
1/2
✓ Branch 1 taken 21108 times.
✗ Branch 2 not taken.
 21108 pointers[i] = ExtractWithHash(key, key_hash);
605 }
606 424 }
607
608 18 void ExtendibleHash::BatchPut(
609 base::ConstArray<Key_t> keys, Value_t* pointers, unsigned tid) {
610
3/6
✓ Branch 0 taken 18 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 18 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 18 times.
 18 if (pointers == nullptr || keys.Size() == 0) {
611 ✗ LOG(FATAL) << "Invalid pointers array or empty keys";
612 }
613
2/2
✓ Branch 1 taken 144 times.
✓ Branch 2 taken 18 times.
 162 for (size_t i = 0; i < keys.Size(); ++i) {
614 144 Key_t key = keys[i];
615 144 Put(key, pointers[i], tid);
616 }
617 18 }
618