GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 0.0% 0 / 0 / 33
Functions: 0.0% 0 / 0 / 12
Branches: 0.0% 0 / 0 / 34
memory/epoch_manager.h
Line Branch Exec Source
1 // Copyright (c) Microsoft Corporation. All rights reserved.
2 // Modified by Minhui Xie
3 // Licensed under the MIT license.
4 #pragma once
5 #include <deque>
6
7 #include "base/base.h"
8 #include "base/hash.h"
9 #include "base/log.h"
10
11 namespace base {
12
13 namespace epoch {
14
15 typedef uint64_t Epoch;
16
17 class MinEpochTable {
18 struct EpochListEntry {
19 static constexpr int kEpochListLength = 16;
20
21 EpochListEntry() { epoch_list_.reset(new std::deque<Epoch>); }
22
23 bool EnqueProtect(Epoch current_epoch) {
24 epoch_list_->push_back(current_epoch);
25 return true;
26 }
27
28 bool DequeUnProtect() {
29 // CHECK(!epoch_list_->empty());
30 epoch_list_->pop_front();
31 return true;
32 }
33
34 Epoch MinEpoch() const {
35 if (epoch_list_->size() == 0)
36 return 0;
37 return *std::min_element(epoch_list_->begin(), epoch_list_->end());
38 }
39
40 int PendingEpochNum() const { return epoch_list_->size(); }
41
42 std::atomic<uint64_t> thread_id_{0};
43 std::unique_ptr<std::deque<Epoch>> epoch_list_;
44 char un_used[48];
45 };
46
47 struct EpochEntry {
48 ✗ EpochEntry() { epoch_ = 0; }
49
50 bool EnqueProtect(Epoch current_epoch) {
51 epoch_ = current_epoch;
52 return true;
53 }
54
55 bool DequeUnProtect() {
56 epoch_ = 0;
57 return true;
58 }
59
60 ✗ Epoch MinEpoch() const { return epoch_; }
61
62 std::atomic<uint64_t> thread_id_{0};
63 std::atomic<Epoch> epoch_;
64 char un_used[48];
65 };
66
67 using Entry = EpochEntry;
68 static_assert(sizeof(Entry) == 64, "Unexpected table entry size");
69
70 public:
71 ✗ MinEpochTable(int max_thread_num = 128) : max_thread_num_(max_thread_num) {
72 // (char[sizeof(Entry)]) "bla";
73 ✗ table_ = new Entry[max_thread_num_];
74 ✗ CHECK(table_);
75 ✗ }
76
77 ✗ ~MinEpochTable() { delete[] table_; }
78
79 bool EnqueProtect(Epoch current_epoch) {
80 Entry* entry = GetEntryForThread();
81 return entry->EnqueProtect(current_epoch);
82 }
83
84 bool PopUnprotect() {
85 Entry* entry = GetEntryForThread();
86 entry->DequeUnProtect();
87 return true;
88 }
89
90 ✗ Epoch ComputeNewSafeToReclaimEpoch(Epoch current_epoch) {
91 ✗ Epoch oldest_call = current_epoch;
92 ✗ for (uint64_t i = 0; i < max_thread_num_; ++i) {
93 ✗ Entry& entry = table_[i];
94 // If any other thread has flushed a protected epoch to the cache
95 // hierarchy we're guaranteed to see it even with relaxed access.
96 ✗ Epoch entryEpoch = entry.MinEpoch();
97 ✗ if (entryEpoch != 0 && entryEpoch < oldest_call) {
98 ✗ oldest_call = entryEpoch;
99 }
100 }
101 // The latest safe epoch is the one just before the earlier unsafe one.
102 ✗ return oldest_call - 1;
103 }
104
105 // int MaxPendingEpochNumPerThread() const {
106 // int ret = 0;
107 // for (uint64_t i = 0; i < max_thread_num_; ++i) {
108 // Entry& entry = table_[i];
109 // ret = std::max(ret, entry.PendingEpochNum());
110 // }
111 // return ret;
112 // }
113
114 private:
115 Entry* GetEntryForThread() {
116 thread_local Entry* thread_local_entry = nullptr;
117 if (thread_local_entry)
118 return thread_local_entry;
119 uint64_t current_thread_id = pthread_self();
120 thread_local_entry = ReserveEntry(
121 GetHash(current_thread_id) % max_thread_num_, current_thread_id);
122 return thread_local_entry;
123 }
124
125 Entry* ReserveEntry(uint64_t start_index, uint64_t thread_id) {
126 auto start_ts = base::GetTimestamp();
127 for (;;) {
128 auto now_ts = base::GetTimestamp();
129 if (now_ts - start_ts > 2 * 1e6) {
130 LOG(FATAL) << "can not ReserveEntry";
131 }
132 // Reserve an entry in the table.
133 for (uint64_t i = 0; i < max_thread_num_; ++i) {
134 uint64_t indexToTest = (start_index + i) % max_thread_num_;
135 Entry& entry = table_[indexToTest];
136 if (entry.thread_id_ == 0) {
137 uint64_t expected = 0;
138 // Atomically grab a slot. No memory barriers needed.
139 // Once the threadId is in place the slot is locked.
140 bool success = entry.thread_id_.compare_exchange_strong(
141 expected, thread_id, std::memory_order_relaxed);
142 if (success) {
143 return &table_[indexToTest];
144 }
145 // Ignore the CAS failure since the entry must be populated,
146 // just move on to the next entry.
147 }
148 }
149 ReclaimOldEntries();
150 }
151 }
152
153 private:
154 void ReclaimOldEntries() {}
155 std::atomic<Epoch> current_epoch_;
156 const int max_thread_num_;
157 Entry* table_;
158 };
159
160 class EpochManager {
161 private:
162 ✗ EpochManager() : current_epoch_{1}, safe_to_reclaim_epoch_{0} {
163 ✗ epoch_table_ = std::make_unique<MinEpochTable>();
164 ✗ }
165
166 public:
167 ✗ static EpochManager* GetInstance() {
168 ✗ static EpochManager instance;
169 ✗ return &instance;
170 }
171
172 ✗ ~EpochManager(){};
173
174 void Protect() {
175 epoch_table_->EnqueProtect(current_epoch_.load(std::memory_order_relaxed));
176 }
177
178 void UnProtect() { epoch_table_->PopUnprotect(); }
179
180 ✗ Epoch GetCurrentEpoch() {
181 ✗ return current_epoch_.load(std::memory_order_seq_cst);
182 }
183
184 ✗ void BumpCurrentEpoch() {
185 ✗ Epoch newEpoch = current_epoch_.fetch_add(1, std::memory_order_seq_cst);
186 ✗ ComputeNewSafeToReclaimEpoch(newEpoch);
187 ✗ }
188
189 ✗ bool IsSafeToReclaim(Epoch epoch) {
190 ✗ return epoch <= safe_to_reclaim_epoch_.load(std::memory_order_relaxed);
191 }
192
193 Epoch GetSafeEpoch4Debug() {
194 return safe_to_reclaim_epoch_.load(std::memory_order_relaxed);
195 }
196
197 ✗ void ComputeNewSafeToReclaimEpoch(Epoch currentEpoch) {
198 ✗ safe_to_reclaim_epoch_.store(
199 epoch_table_->ComputeNewSafeToReclaimEpoch(currentEpoch),
200 std::memory_order_release);
201 ✗ }
202
203 // int MaxPendingEpochNumPerThread() const {
204 // return epoch_table_->MaxPendingEpochNumPerThread();
205 // }
206
207 private:
208 std::atomic<Epoch> current_epoch_;
209 std::atomic<Epoch> safe_to_reclaim_epoch_;
210 std::unique_ptr<MinEpochTable> epoch_table_;
211 DISALLOW_COPY_AND_ASSIGN(EpochManager);
212 };
213
214 class IGarbageList {
215 public:
216 typedef void (*DestroyCallback)(void* callback_context, void* object);
217
218 IGarbageList() {}
219
220 virtual ~IGarbageList() {}
221
222 virtual bool
223 Initialize(EpochManager* epoch_manager, size_t size = 4 * 1024 * 1024) {
224 (epoch_manager);
225 (size);
226 return true;
227 }
228
229 virtual bool Uninitialize() { return true; }
230
231 virtual bool
232 Push(void* removed_item, DestroyCallback destroy_callback, void* context) = 0;
233 };
234
235 } // namespace epoch
236 } // namespace base
237