]>
Commit | Line | Data |
---|---|---|
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- | |
2 | // vim: ts=8 sw=2 smarttab | |
3 | ||
4 | #include "rgw_period_history.h" | |
5 | #include "rgw_rados.h" | |
6 | ||
7 | #include "include/assert.h" | |
8 | ||
9 | #define dout_subsys ceph_subsys_rgw | |
10 | ||
11 | #undef dout_prefix | |
12 | #define dout_prefix (*_dout << "rgw period history: ") | |
13 | ||
14 | /// an ordered history of consecutive periods | |
15 | class RGWPeriodHistory::History : public bi::avl_set_base_hook<> { | |
16 | public: | |
17 | std::deque<RGWPeriod> periods; | |
18 | ||
19 | epoch_t get_oldest_epoch() const { | |
20 | return periods.front().get_realm_epoch(); | |
21 | } | |
22 | epoch_t get_newest_epoch() const { | |
23 | return periods.back().get_realm_epoch(); | |
24 | } | |
25 | bool contains(epoch_t epoch) const { | |
26 | return get_oldest_epoch() <= epoch && epoch <= get_newest_epoch(); | |
27 | } | |
28 | RGWPeriod& get(epoch_t epoch) { | |
29 | return periods[epoch - get_oldest_epoch()]; | |
30 | } | |
31 | const RGWPeriod& get(epoch_t epoch) const { | |
32 | return periods[epoch - get_oldest_epoch()]; | |
33 | } | |
34 | const std::string& get_predecessor_id() const { | |
35 | return periods.front().get_predecessor(); | |
36 | } | |
37 | }; | |
38 | ||
39 | /// value comparison for avl_set | |
40 | bool operator<(const RGWPeriodHistory::History& lhs, | |
41 | const RGWPeriodHistory::History& rhs) | |
42 | { | |
43 | return lhs.get_newest_epoch() < rhs.get_newest_epoch(); | |
44 | } | |
45 | ||
46 | /// key-value comparison for avl_set | |
47 | struct NewestEpochLess { | |
48 | bool operator()(const RGWPeriodHistory::History& value, epoch_t key) const { | |
49 | return value.get_newest_epoch() < key; | |
50 | } | |
51 | }; | |
52 | ||
53 | ||
54 | using Cursor = RGWPeriodHistory::Cursor; | |
55 | ||
56 | const RGWPeriod& Cursor::get_period() const | |
57 | { | |
58 | std::lock_guard<std::mutex> lock(*mutex); | |
59 | return history->get(epoch); | |
60 | } | |
61 | bool Cursor::has_prev() const | |
62 | { | |
63 | std::lock_guard<std::mutex> lock(*mutex); | |
64 | return epoch > history->get_oldest_epoch(); | |
65 | } | |
66 | bool Cursor::has_next() const | |
67 | { | |
68 | std::lock_guard<std::mutex> lock(*mutex); | |
69 | return epoch < history->get_newest_epoch(); | |
70 | } | |
71 | ||
72 | bool operator==(const Cursor& lhs, const Cursor& rhs) | |
73 | { | |
74 | return lhs.history == rhs.history && lhs.epoch == rhs.epoch; | |
75 | } | |
76 | ||
77 | bool operator!=(const Cursor& lhs, const Cursor& rhs) | |
78 | { | |
79 | return !(lhs == rhs); | |
80 | } | |
81 | ||
82 | class RGWPeriodHistory::Impl final { | |
83 | public: | |
84 | Impl(CephContext* cct, Puller* puller, const RGWPeriod& current_period); | |
85 | ~Impl(); | |
86 | ||
87 | Cursor get_current() const { return current_cursor; } | |
88 | Cursor attach(RGWPeriod&& period); | |
89 | Cursor insert(RGWPeriod&& period); | |
90 | Cursor lookup(epoch_t realm_epoch); | |
91 | ||
92 | private: | |
93 | /// an intrusive set of histories, ordered by their newest epoch. although | |
94 | /// the newest epoch of each history is mutable, the ordering cannot change | |
95 | /// because we prevent the histories from overlapping | |
96 | using Set = bi::avl_set<RGWPeriodHistory::History>; | |
97 | ||
98 | /// insert the given period into the period history, creating new unconnected | |
99 | /// histories or merging existing histories as necessary. expects the caller | |
100 | /// to hold a lock on mutex. returns a valid cursor regardless of whether it | |
101 | /// ends up in current_history, though cursors in other histories are only | |
102 | /// valid within the context of the lock | |
103 | Cursor insert_locked(RGWPeriod&& period); | |
104 | ||
105 | /// merge the periods from the src history onto the end of the dst history, | |
106 | /// and return an iterator to the merged history | |
107 | Set::iterator merge(Set::iterator dst, Set::iterator src); | |
108 | ||
109 | /// construct a Cursor object using Cursor's private constuctor | |
110 | Cursor make_cursor(Set::const_iterator history, epoch_t epoch); | |
111 | ||
112 | CephContext *const cct; | |
113 | Puller *const puller; //< interface for pulling missing periods | |
114 | Cursor current_cursor; //< Cursor to realm's current period | |
115 | ||
116 | mutable std::mutex mutex; //< protects the histories | |
117 | ||
118 | /// set of disjoint histories that are missing intermediate periods needed to | |
119 | /// connect them together | |
120 | Set histories; | |
121 | ||
122 | /// iterator to the history that contains the realm's current period | |
123 | Set::const_iterator current_history; | |
124 | }; | |
125 | ||
126 | RGWPeriodHistory::Impl::Impl(CephContext* cct, Puller* puller, | |
127 | const RGWPeriod& current_period) | |
128 | : cct(cct), puller(puller) | |
129 | { | |
130 | if (!current_period.get_id().empty()) { | |
131 | // copy the current period into a new history | |
132 | auto history = new History; | |
133 | history->periods.push_back(current_period); | |
134 | ||
135 | // insert as our current history | |
136 | current_history = histories.insert(*history).first; | |
137 | ||
138 | // get a cursor to the current period | |
139 | current_cursor = make_cursor(current_history, current_period.get_realm_epoch()); | |
140 | } else { | |
141 | current_history = histories.end(); | |
142 | } | |
143 | } | |
144 | ||
145 | RGWPeriodHistory::Impl::~Impl() | |
146 | { | |
147 | // clear the histories and delete each entry | |
148 | histories.clear_and_dispose(std::default_delete<History>{}); | |
149 | } | |
150 | ||
151 | Cursor RGWPeriodHistory::Impl::attach(RGWPeriod&& period) | |
152 | { | |
153 | if (current_history == histories.end()) { | |
154 | return Cursor{-EINVAL}; | |
155 | } | |
156 | ||
157 | const auto epoch = period.get_realm_epoch(); | |
158 | ||
159 | std::string predecessor_id; | |
160 | for (;;) { | |
161 | { | |
162 | // hold the lock over insert, and while accessing the unsafe cursor | |
163 | std::lock_guard<std::mutex> lock(mutex); | |
164 | ||
165 | auto cursor = insert_locked(std::move(period)); | |
166 | if (!cursor) { | |
167 | return cursor; | |
168 | } | |
169 | if (current_history->contains(epoch)) { | |
170 | break; // the history is complete | |
171 | } | |
172 | ||
173 | // take the predecessor id of the most recent history | |
174 | if (cursor.get_epoch() > current_cursor.get_epoch()) { | |
175 | predecessor_id = cursor.history->get_predecessor_id(); | |
176 | } else { | |
177 | predecessor_id = current_history->get_predecessor_id(); | |
178 | } | |
179 | } | |
180 | ||
181 | if (predecessor_id.empty()) { | |
182 | lderr(cct) << "reached a period with an empty predecessor id" << dendl; | |
183 | return Cursor{-EINVAL}; | |
184 | } | |
185 | ||
186 | // pull the period outside of the lock | |
187 | int r = puller->pull(predecessor_id, period); | |
188 | if (r < 0) { | |
189 | return Cursor{r}; | |
190 | } | |
191 | } | |
192 | ||
193 | // return a cursor to the requested period | |
194 | return make_cursor(current_history, epoch); | |
195 | } | |
196 | ||
197 | Cursor RGWPeriodHistory::Impl::insert(RGWPeriod&& period) | |
198 | { | |
199 | if (current_history == histories.end()) { | |
200 | return Cursor{-EINVAL}; | |
201 | } | |
202 | ||
203 | std::lock_guard<std::mutex> lock(mutex); | |
204 | ||
205 | auto cursor = insert_locked(std::move(period)); | |
206 | ||
207 | if (cursor.get_error()) { | |
208 | return cursor; | |
209 | } | |
210 | // we can only provide cursors that are safe to use outside of the mutex if | |
211 | // they're within the current_history, because other histories can disappear | |
212 | // in a merge. see merge() for the special handling of current_history | |
213 | if (cursor.history == &*current_history) { | |
214 | return cursor; | |
215 | } | |
216 | return Cursor{}; | |
217 | } | |
218 | ||
219 | Cursor RGWPeriodHistory::Impl::lookup(epoch_t realm_epoch) | |
220 | { | |
221 | if (current_history != histories.end() && | |
222 | current_history->contains(realm_epoch)) { | |
223 | return make_cursor(current_history, realm_epoch); | |
224 | } | |
225 | return Cursor{}; | |
226 | } | |
227 | ||
228 | Cursor RGWPeriodHistory::Impl::insert_locked(RGWPeriod&& period) | |
229 | { | |
230 | auto epoch = period.get_realm_epoch(); | |
231 | ||
232 | // find the first history whose newest epoch comes at or after this period | |
233 | auto i = histories.lower_bound(epoch, NewestEpochLess{}); | |
234 | ||
235 | if (i == histories.end()) { | |
236 | // epoch is past the end of our newest history | |
237 | auto last = --Set::iterator{i}; // last = i - 1 | |
238 | ||
239 | if (epoch == last->get_newest_epoch() + 1) { | |
240 | // insert at the back of the last history | |
241 | last->periods.emplace_back(std::move(period)); | |
242 | return make_cursor(last, epoch); | |
243 | } | |
244 | ||
245 | // create a new history for this period | |
246 | auto history = new History; | |
247 | history->periods.emplace_back(std::move(period)); | |
248 | histories.insert(last, *history); | |
249 | ||
250 | i = Set::s_iterator_to(*history); | |
251 | return make_cursor(i, epoch); | |
252 | } | |
253 | ||
254 | if (i->contains(epoch)) { | |
255 | // already resident in this history | |
256 | auto& existing = i->get(epoch); | |
257 | // verify that the period ids match; otherwise we've forked the history | |
258 | if (period.get_id() != existing.get_id()) { | |
259 | lderr(cct) << "Got two different periods, " << period.get_id() | |
260 | << " and " << existing.get_id() << ", with the same realm epoch " | |
261 | << epoch << "! This indicates a fork in the period history." << dendl; | |
262 | return Cursor{-EEXIST}; | |
263 | } | |
264 | // update the existing period if we got a newer period epoch | |
265 | if (period.get_epoch() > existing.get_epoch()) { | |
266 | existing = std::move(period); | |
267 | } | |
268 | return make_cursor(i, epoch); | |
269 | } | |
270 | ||
271 | if (epoch + 1 == i->get_oldest_epoch()) { | |
272 | // insert at the front of this history | |
273 | i->periods.emplace_front(std::move(period)); | |
274 | ||
275 | // try to merge with the previous history | |
276 | if (i != histories.begin()) { | |
277 | auto prev = --Set::iterator{i}; | |
278 | if (epoch == prev->get_newest_epoch() + 1) { | |
279 | i = merge(prev, i); | |
280 | } | |
281 | } | |
282 | return make_cursor(i, epoch); | |
283 | } | |
284 | ||
285 | if (i != histories.begin()) { | |
286 | auto prev = --Set::iterator{i}; | |
287 | if (epoch == prev->get_newest_epoch() + 1) { | |
288 | // insert at the back of the previous history | |
289 | prev->periods.emplace_back(std::move(period)); | |
290 | return make_cursor(prev, epoch); | |
291 | } | |
292 | } | |
293 | ||
294 | // create a new history for this period | |
295 | auto history = new History; | |
296 | history->periods.emplace_back(std::move(period)); | |
297 | histories.insert(i, *history); | |
298 | ||
299 | i = Set::s_iterator_to(*history); | |
300 | return make_cursor(i, epoch); | |
301 | } | |
302 | ||
303 | RGWPeriodHistory::Impl::Set::iterator | |
304 | RGWPeriodHistory::Impl::merge(Set::iterator dst, Set::iterator src) | |
305 | { | |
306 | assert(dst->get_newest_epoch() + 1 == src->get_oldest_epoch()); | |
307 | ||
308 | // always merge into current_history | |
309 | if (src == current_history) { | |
310 | // move the periods from dst onto the front of src | |
311 | src->periods.insert(src->periods.begin(), | |
312 | std::make_move_iterator(dst->periods.begin()), | |
313 | std::make_move_iterator(dst->periods.end())); | |
314 | histories.erase_and_dispose(dst, std::default_delete<History>{}); | |
315 | return src; | |
316 | } | |
317 | ||
318 | // move the periods from src onto the end of dst | |
319 | dst->periods.insert(dst->periods.end(), | |
320 | std::make_move_iterator(src->periods.begin()), | |
321 | std::make_move_iterator(src->periods.end())); | |
322 | histories.erase_and_dispose(src, std::default_delete<History>{}); | |
323 | return dst; | |
324 | } | |
325 | ||
326 | Cursor RGWPeriodHistory::Impl::make_cursor(Set::const_iterator history, | |
327 | epoch_t epoch) { | |
328 | return Cursor{&*history, &mutex, epoch}; | |
329 | } | |
330 | ||
331 | ||
332 | RGWPeriodHistory::RGWPeriodHistory(CephContext* cct, Puller* puller, | |
333 | const RGWPeriod& current_period) | |
334 | : impl(new Impl(cct, puller, current_period)) {} | |
335 | ||
336 | RGWPeriodHistory::~RGWPeriodHistory() = default; | |
337 | ||
338 | Cursor RGWPeriodHistory::get_current() const | |
339 | { | |
340 | return impl->get_current(); | |
341 | } | |
342 | Cursor RGWPeriodHistory::attach(RGWPeriod&& period) | |
343 | { | |
344 | return impl->attach(std::move(period)); | |
345 | } | |
346 | Cursor RGWPeriodHistory::insert(RGWPeriod&& period) | |
347 | { | |
348 | return impl->insert(std::move(period)); | |
349 | } | |
350 | Cursor RGWPeriodHistory::lookup(epoch_t realm_epoch) | |
351 | { | |
352 | return impl->lookup(realm_epoch); | |
353 | } |