GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 70.7% 193 / 0 / 273
Functions: 76.0% 19 / 0 / 25
Branches: 53.3% 112 / 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 97216 static inline uint64_t mypow(uint64_t x, unsigned int y) noexcept {
12
1/2
✓ Branch 0 taken 97216 times.
✗ Branch 1 not taken.
 97216 if (x == 2) {
13
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 97216 times.
 97216 if (y >= 64)
14 ✗ return std::numeric_limits<uint64_t>::max();
15 97216 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 99368 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 6702 times.
✓ Branch 1 taken 92666 times.
 99368 if (sema == -1)
100 6702 return -2;
101 # ifdef LSB
102
2/2
✓ Branch 1 taken 22 times.
✓ Branch 2 taken 92644 times.
 92666 if ((key_hash & (size_t)mypow(2, local_depth) - 1) != pattern)
103 22 return -2;
104 # else
105 if ((key_hash >> (8 * sizeof(key_hash) - local_depth)) != pattern)
106 return -2;
107 # endif
108 92644 auto lock = sema;
109
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 92636 times.
 92644 if (lock < 0)
110 8 return -2;
111 92636 int ret = -1;
112
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 92634 times.
 92718 while (!CAS(&sema, &lock, lock + 1)) {
113 84 lock = sema;
114
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 82 times.
 84 if (lock < 0)
115 2 return -2;
116 }
117
2/2
✓ Branch 0 taken 1179074 times.
✓ Branch 1 taken 61248 times.
 1240322 for (unsigned i = 0; i < kNumSlot; ++i) {
118
2/2
✓ Branch 0 taken 31386 times.
✓ Branch 1 taken 1147688 times.
 1179074 if (_[i].key == key) {
119 Value_t previous =
120 31386 __atomic_exchange_n(&_[i].value, value, __ATOMIC_ACQ_REL);
121
1/2
✓ Branch 0 taken 31386 times.
✗ Branch 1 not taken.
 31386 if (old_value != nullptr) {
122 31386 *old_value = previous;
123 }
124 31386 ret = i;
125 31386 lock = sema;
126
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 31386 times.
 31400 while (!CAS(&sema, &lock, lock - 1)) {
127 14 lock = sema;
128 }
129 31386 return ret;
130 }
131 }
132 61248 Key_t LOCK = INVALID;
133
2/2
✓ Branch 0 taken 733162 times.
✓ Branch 1 taken 7150 times.
 740312 for (unsigned i = 0; i < kNumSlot; ++i) {
134
2/2
✓ Branch 0 taken 54098 times.
✓ Branch 1 taken 679064 times.
 733162 if (CAS(&_[i].key, &LOCK, SENTINEL)) {
135 54098 _[i].value = value;
136 54098 mfence();
137 54098 _[i].key = key;
138 54098 ret = i;
139 54098 break;
140 } else {
141 679064 LOCK = INVALID;
142 }
143 }
144 61248 lock = sema;
145
2/2
✓ Branch 0 taken 46 times.
✓ Branch 1 taken 61248 times.
 61294 while (!CAS(&sema, &lock, lock - 1)) {
146 46 lock = sema;
147 }
148 61248 return ret;
149 #endif
150 }
151
152 72800 void Block::Insert4split(Key_t& key, Value_t value) {
153
1/2
✓ Branch 0 taken 343214 times.
✗ Branch 1 not taken.
 343214 for (unsigned i = 0; i < kNumSlot; ++i) {
154
2/2
✓ Branch 0 taken 72800 times.
✓ Branch 1 taken 270414 times.
 343214 if (_[i].key == INVALID) {
155 72800 _[i].key = key;
156 72800 _[i].value = value;
157 72800 return;
158 }
159 }
160 }
161
162 7150 Block** Block::Split(void) {
163 using namespace std;
164 7150 int64_t lock = 0;
165
2/2
✓ Branch 0 taken 2600 times.
✓ Branch 1 taken 4550 times.
 7150 if (!CAS(&sema, &lock, -1))
166 2600 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 4550 times.
✗ Branch 2 not taken.
 4550 Block** split = new Block*[2];
191
1/2
✓ Branch 1 taken 4550 times.
✗ Branch 2 not taken.
 4550 split[0] = new Block(local_depth + 1);
192
1/2
✓ Branch 1 taken 4550 times.
✗ Branch 2 not taken.
 4550 split[1] = new Block(local_depth + 1);
193
194
2/2
✓ Branch 0 taken 72800 times.
✓ Branch 1 taken 4550 times.
 77350 for (unsigned i = 0; i < kNumSlot; ++i) {
195
1/2
✓ Branch 1 taken 72800 times.
✗ Branch 2 not taken.
 72800 auto key_hash = h(&_[i].key, sizeof(Key_t));
196 # ifdef LSB
197
2/2
✓ Branch 0 taken 35918 times.
✓ Branch 1 taken 36882 times.
 72800 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 35918 times.
✗ Branch 2 not taken.
 35918 split[1]->Insert4split(_[i].key, _[i].value);
202 } else {
203
1/2
✓ Branch 1 taken 36882 times.
✗ Branch 2 not taken.
 36882 split[0]->Insert4split(_[i].key, _[i].value);
204 }
205 }
206
207 4550 clflush((char*)split[0], sizeof(Block));
208 4550 clflush((char*)split[1], sizeof(Block));
209
210 4550 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 364 ExtendibleHash::ExtendibleHash(const BaseKVConfig& config)
245 : Index(config),
246
1/2
✓ Branch 1 taken 364 times.
✗ Branch 2 not taken.
 364 dir{[&config]() -> size_t {
247
2/2
✓ Branch 1 taken 334 times.
✓ Branch 2 taken 30 times.
 364 if (!config.json_config_.contains("initial_capacity")) {
248
2/4
✓ Branch 2 taken 334 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 334 times.
✗ Branch 6 not taken.
 334 LOG(WARNING) << "ExtendibleHash config missing 'initial_capacity'";
249 334 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 364 times.
✗ Branch 3 not taken.
 364 global_depth{0} {
261 // Customize based on config, e.g.
262
3/6
✓ Branch 1 taken 364 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 364 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 364 times.
✗ Branch 8 not taken.
 364 LOG(INFO) << "DRAM index init";
263 364 global_depth = static_cast<size_t>(log2(dir.capacity));
264
2/2
✓ Branch 0 taken 814 times.
✓ Branch 1 taken 364 times.
 1178 for (unsigned i = 0; i < dir.capacity; ++i) {
265
1/2
✓ Branch 1 taken 814 times.
✗ Branch 2 not taken.
 814 dir._[i] = new Block(global_depth);
266 814 dir._[i]->pattern = i;
267 }
268 364 }
269
270 728 ExtendibleHash::~ExtendibleHash() {}
271
272 6976 void Directory::LSBUpdate(
273 int local_depth, int global_depth, int dir_cap, int x, Block** s) {
274 6976 int depth_diff = global_depth - local_depth;
275
2/2
✓ Branch 0 taken 5522 times.
✓ Branch 1 taken 1454 times.
 6976 if (depth_diff == 0) {
276
2/2
✓ Branch 0 taken 2424 times.
✓ Branch 1 taken 3098 times.
 5522 if ((x % dir_cap) >= dir_cap / 2) {
277 2424 _[x - dir_cap / 2] = s[0];
278 2424 clflush((char*)&_[x - dir_cap / 2], sizeof(Block*));
279 2424 _[x] = s[1];
280 2424 clflush((char*)&_[x], sizeof(Block*));
281 } else {
282 3098 _[x] = s[0];
283 3098 clflush((char*)&_[x], sizeof(Block*));
284 3098 _[x + dir_cap / 2] = s[1];
285 3098 clflush((char*)&_[x + dir_cap / 2], sizeof(Block*));
286 }
287 } else {
288
2/2
✓ Branch 0 taken 776 times.
✓ Branch 1 taken 678 times.
 1454 if ((x % dir_cap) >= dir_cap / 2) {
289 776 LSBUpdate(local_depth + 1, global_depth, dir_cap / 2, x - dir_cap / 2, s);
290 776 LSBUpdate(local_depth + 1, global_depth, dir_cap / 2, x, s);
291 } else {
292 678 LSBUpdate(local_depth + 1, global_depth, dir_cap / 2, x, s);
293 678 LSBUpdate(local_depth + 1, global_depth, dir_cap / 2, x + dir_cap / 2, s);
294 }
295 }
296 6976 return;
297 }
298
299 85484 Value_t ExtendibleHash::Insert(Key_t& key, Value_t value) {
300 using namespace std;
301
1/2
✓ Branch 1 taken 85484 times.
✗ Branch 2 not taken.
 85484 auto key_hash = h(&key, sizeof(key));
302 85484 Value_t old_value = kValueHandleNone;
303
304 99368 RETRY:
305 #ifdef LSB
306 // auto x = (key_hash & (pow(2, global_depth)-1));
307 99368 auto x = (key_hash % dir.capacity);
308 #else
309 auto x = (key_hash >> (8 * sizeof(key_hash) - global_depth));
310 #endif
311 99368 auto target = dir._[x];
312
1/2
✓ Branch 1 taken 99368 times.
✗ Branch 2 not taken.
 99368 auto ret = target->Insert(key, value, key_hash, &old_value);
313
314
2/2
✓ Branch 0 taken 7150 times.
✓ Branch 1 taken 92218 times.
 99368 if (ret == -1) {
315
1/2
✓ Branch 1 taken 7150 times.
✗ Branch 2 not taken.
 7150 Block** s = target->Split();
316
2/2
✓ Branch 0 taken 2600 times.
✓ Branch 1 taken 4550 times.
 7150 if (s == nullptr) {
317 // another thread is doing split
318 2600 goto RETRY;
319 }
320
321 #ifdef LSB
322 4550 s[0]->pattern = (key_hash % (size_t)mypow(2, s[0]->local_depth - 1));
323 4550 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 1394 times.
✓ Branch 2 taken 4550 times.
 5944 while (!dir.Acquire()) {
333 // lockCount ++;
334 }
335 // dir.sema++;
336 { // CRITICAL SECTION - directory update
337 // auto prev = x;
338 #ifdef LSB
339 4550 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 4068 times.
✓ Branch 1 taken 482 times.
 4550 if (dir._[x]->local_depth < global_depth) { // normal split
347 #endif
348 #ifdef LSB
349
1/2
✓ Branch 1 taken 4068 times.
✗ Branch 2 not taken.
 4068 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 482 auto d = dir._;
390
2/4
✓ Branch 0 taken 482 times.
✗ Branch 1 not taken.
✓ Branch 4 taken 482 times.
✗ Branch 5 not taken.
 482 auto _dir = new Block*[dir.capacity * 2];
391 #ifdef LSB
392 482 memcpy(_dir, d, sizeof(Block*) * dir.capacity);
393 482 memcpy(_dir + dir.capacity, d, sizeof(Block*) * dir.capacity);
394 482 _dir[x] = s[0];
395 482 _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 482 clflush((char*)&dir._[0], sizeof(Block*) * dir.capacity);
408 482 dir._ = _dir;
409 482 clflush((char*)&dir._, sizeof(void*));
410 482 dir.capacity *= 2;
411 482 clflush((char*)&dir.capacity, sizeof(size_t));
412 482 global_depth += 1;
413 482 clflush((char*)&global_depth, sizeof(global_depth));
414
1/2
✓ Branch 0 taken 482 times.
✗ Branch 1 not taken.
 482 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 4550 times.
 4550 while (!dir.Release()) {
425 // lockCount ++;
426 }
427 4550 goto RETRY;
428
2/2
✓ Branch 0 taken 6734 times.
✓ Branch 1 taken 85484 times.
 92218 } else if (ret == -2) {
429 // Block is splitting or directory pointers are stale; retry without
430 // recursion.
431
2/2
✓ Branch 0 taken 6712 times.
✓ Branch 1 taken 22 times.
 6734 if (target->sema == -1) {
432 6712 std::this_thread::yield();
433 }
434 6734 goto RETRY;
435 } else {
436 85484 clflush((char*)&dir._[x]->_[ret], sizeof(Pair));
437 }
438 85484 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 85960 size_t ExtendibleHash::DirectoryIndex(size_t key_hash) const {
479 #ifdef LSB
480 85960 return key_hash % dir.capacity;
481 #else
482 return key_hash >> (8 * sizeof(key_hash) - global_depth);
483 #endif
484 }
485
486 66374 Value_t ExtendibleHash::ExtractWithHash(Key_t& key, size_t key_hash) {
487 66374 auto x = DirectoryIndex(key_hash);
488
489 66374 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 433250 times.
✓ Branch 1 taken 1400 times.
 434650 for (unsigned i = 0; i < Block::kNumSlot; ++i) {
499
2/2
✓ Branch 0 taken 64974 times.
✓ Branch 1 taken 368276 times.
 433250 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 64974 return dir_->_[i].value;
507 }
508 368276 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 1400 return NONE;
518 }
519
520 45288 Value_t ExtendibleHash::Extract(Key_t& key) {
521 45288 auto key_hash = h(&key, sizeof(key));
522 45288 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 45288 void ExtendibleHash::Get(Key_t key, Value_t& pointer, unsigned tid) {
575 45288 pointer = Extract(key);
576 45288 }
577
578 85484 Value_t ExtendibleHash::Put(Key_t key, Value_t pointer, unsigned tid) {
579 85484 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 412 void ExtendibleHash::BatchGet(
592 base::ConstArray<Key_t> keys, Value_t* pointers, unsigned tid) {
593
3/6
✓ Branch 0 taken 412 times.
✗ Branch 1 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 412 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 412 times.
 412 if (pointers == nullptr || keys.Size() == 0) {
594 ✗ LOG(FATAL) << "Invalid pointers array or empty keys";
595 }
596 412 constexpr size_t kPrefetchDistance = 4;
597
2/2
✓ Branch 1 taken 21086 times.
✓ Branch 2 taken 412 times.
 21498 for (size_t i = 0; i < keys.Size(); ++i) {
598 21086 Key_t key = keys[static_cast<int>(i)];
599
1/2
✓ Branch 1 taken 21086 times.
✗ Branch 2 not taken.
 21086 auto key_hash = h(&key, sizeof(key));
600
2/2
✓ Branch 1 taken 19586 times.
✓ Branch 2 taken 1500 times.
 21086 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 21086 times.
✗ Branch 2 not taken.
 21086 pointers[i] = ExtractWithHash(key, key_hash);
605 }
606 412 }
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