GCC Code Coverage Report

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