GCC Code Coverage Report

src/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
23 / 25
92.0%
Branches:
10 / 18
55.6%
Functions:
8 / 8
100.0%
storage/index/dram/extendible_hash.h
Line Branch Exec Source
1 #pragma once
2
3 #include <cstdint>
4 #include <cstdlib>
5 #include <cstring>
6 #include <new>
7 #include "../index.h"
8 #include "base/factory.h"
9 #include "storage/kv_engine/base_kv.h"
10 #include "../utils/util.h"
11 #define LSB
12
13 // Diagnostic counters for the insert path; only maintained when
14 // RECSTORE_EXTENDIBLE_HASH_COUNTERS is set (see extendible_hash.cpp).
15 struct ExtendibleHashInsertCounters {
16 std::uint64_t insert_calls = 0;
17 std::uint64_t split_calls = 0;
18 std::uint64_t split_ns = 0;
19 };
20
21 void GetExtendibleHashInsertCounters(ExtendibleHashInsertCounters* out);
22
23 const size_t kMask = 256 - 1;
24 const size_t kShift = 8;
25
26 struct Block {
27 static const size_t kBlockSize = 256; // 4 - 1
28 // static const size_t kBlockSize = 1024; // 16 - 1
29 // static const size_t kBlockSize = 4*1024; // 64 - 1
30 // static const size_t kBlockSize = 16*1024; // 256 - 1
31 // static const size_t kBlockSize = 64*1024; // 1024 - 1
32 // static const size_t kBlockSize = 256 * 1024; // 4096 - 1
33 static const size_t kNumSlot = kBlockSize / sizeof(Pair);
34
35 Block(void) : local_depth{0} {}
36
37
2/2
✓ Branch 1 taken 159360 times.
✓ Branch 2 taken 9960 times.
 169320 Block(size_t depth) : local_depth{depth} {}
38
39 ~Block(void) {}
40
41 9960 void* operator new(size_t size) {
42 9960 void* ret = nullptr;
43
3/6
✓ Branch 0 taken 9960 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 9960 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 9960 times.
 9960 if (posix_memalign(&ret, 64, size) != 0 || ret == nullptr)
44 ✗ throw std::bad_alloc();
45 9960 return ret;
46 }
47
48 void* operator new[](size_t size) {
49 void* ret = nullptr;
50 if (posix_memalign(&ret, 64, size) != 0 || ret == nullptr)
51 throw std::bad_alloc();
52 return ret;
53 }
54
55 int Insert(Key_t&, Value_t, size_t, Value_t* old_value = nullptr);
56 void Insert4split(Key_t&, Value_t);
57 bool Put(Key_t&, Value_t, size_t);
58 Block** Split(void);
59 bool Delete(Key_t&);
60
61 void operator delete[](void* p) noexcept { std::free(p); }
62 void operator delete[](void* p, std::size_t) noexcept { std::free(p); }
63 void operator delete(void* p) noexcept { std::free(p); }
64 void operator delete(void* p, std::size_t) noexcept { std::free(p); }
65
66 Pair _[kNumSlot];
67 size_t local_depth;
68 int64_t sema = 0;
69 size_t pattern = 0;
70 size_t numElem(void);
71 };
72
73 struct Directory {
74 static const size_t kDefaultDirectorySize = 1024;
75 Block** _;
76 size_t capacity;
77 bool lock;
78 int sema = 0;
79
80 Directory(void) {
81 capacity = kDefaultDirectorySize;
82 _ = new Block*[capacity];
83 lock = false;
84 sema = 0;
85 }
86
87 386 Directory(size_t size) {
88 386 capacity = size;
89
1/2
✓ Branch 0 taken 386 times.
✗ Branch 1 not taken.
 386 _ = new Block*[capacity];
90 386 lock = false;
91 386 sema = 0;
92 386 }
93
94
1/2
✓ Branch 0 taken 386 times.
✗ Branch 1 not taken.
 386 ~Directory(void) { delete[] _; }
95
96 11988 bool Acquire(void) {
97 11988 bool unlocked = false;
98 11988 return CAS(&lock, &unlocked, true);
99 }
100
101 4562 bool Release(void) {
102 4562 bool locked = true;
103 4562 return CAS(&lock, &locked, false);
104 }
105
106 void SanityCheck(void*);
107 void LSBUpdate(int, int, int, int, Block**);
108 };
109
110 class ExtendibleHash : public Index {
111 public:
112 ExtendibleHash(const BaseKVConfig& config);
113 ~ExtendibleHash();
114 bool Delete(Key_t&) override;
115 double Utilization(void) override;
116 size_t Capacity(void) override;
117 void Get(Key_t key, Value_t& value, unsigned tid) override;
118 Value_t Put(Key_t key, Value_t value, unsigned tid) override;
119 void BatchGet(base::ConstArray<Key_t> keys,
120 Value_t* pointers,
121 unsigned tid) override;
122 void BatchPut(base::ConstArray<Key_t> keys,
123 Value_t* pointers,
124 unsigned tid) override;
125
126 386 void operator delete(void* p) noexcept { std::free(p); }
127 void operator delete(void* p, std::size_t) noexcept { std::free(p); }
128 386 void* operator new(size_t size) {
129 386 void* ret = nullptr;
130
3/6
✓ Branch 0 taken 386 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 386 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 386 times.
 386 if (posix_memalign(&ret, 64, size) != 0 || ret == nullptr)
131 ✗ throw std::bad_alloc();
132 386 return ret;
133 }
134
135 private:
136 Directory dir;
137 size_t global_depth;
138
139 size_t DirectoryIndex(size_t key_hash) const;
140 void HintPrefetch(size_t key_hash) const;
141 Value_t ExtractWithHash(Key_t& key, size_t key_hash);
142 Value_t Extract(Key_t& key);
143 Value_t Insert(Key_t& key, Value_t value);
144 bool InsertOnly(Key_t& key, Value_t value);
145 Value_t FindAnyway(Key_t&);
146 };
147