1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab ft=cpp
4 #include "rgw_period_history.h"
7 #include "include/ceph_assert.h"
9 #define dout_subsys ceph_subsys_rgw
12 #define dout_prefix (*_dout << "rgw period history: ")
14 /// an ordered history of consecutive periods
15 class RGWPeriodHistory::History
: public bi::avl_set_base_hook
<> {
17 std::deque
<RGWPeriod
> periods
;
19 epoch_t
get_oldest_epoch() const {
20 return periods
.front().get_realm_epoch();
22 epoch_t
get_newest_epoch() const {
23 return periods
.back().get_realm_epoch();
25 bool contains(epoch_t epoch
) const {
26 return get_oldest_epoch() <= epoch
&& epoch
<= get_newest_epoch();
28 RGWPeriod
& get(epoch_t epoch
) {
29 return periods
[epoch
- get_oldest_epoch()];
31 const RGWPeriod
& get(epoch_t epoch
) const {
32 return periods
[epoch
- get_oldest_epoch()];
34 const std::string
& get_predecessor_id() const {
35 return periods
.front().get_predecessor();
39 /// value comparison for avl_set
40 bool operator<(const RGWPeriodHistory::History
& lhs
,
41 const RGWPeriodHistory::History
& rhs
)
43 return lhs
.get_newest_epoch() < rhs
.get_newest_epoch();
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
;
54 using Cursor
= RGWPeriodHistory::Cursor
;
56 const RGWPeriod
& Cursor::get_period() const
58 std::lock_guard
<std::mutex
> lock(*mutex
);
59 return history
->get(epoch
);
61 bool Cursor::has_prev() const
63 std::lock_guard
<std::mutex
> lock(*mutex
);
64 return epoch
> history
->get_oldest_epoch();
66 bool Cursor::has_next() const
68 std::lock_guard
<std::mutex
> lock(*mutex
);
69 return epoch
< history
->get_newest_epoch();
72 bool operator==(const Cursor
& lhs
, const Cursor
& rhs
)
74 return lhs
.history
== rhs
.history
&& lhs
.epoch
== rhs
.epoch
;
77 bool operator!=(const Cursor
& lhs
, const Cursor
& rhs
)
82 class RGWPeriodHistory::Impl final
{
84 Impl(CephContext
* cct
, Puller
* puller
, const RGWPeriod
& current_period
);
87 Cursor
get_current() const { return current_cursor
; }
88 Cursor
attach(RGWPeriod
&& period
, optional_yield y
);
89 Cursor
insert(RGWPeriod
&& period
);
90 Cursor
lookup(epoch_t realm_epoch
);
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
>;
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
);
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
);
109 /// construct a Cursor object using Cursor's private constuctor
110 Cursor
make_cursor(Set::const_iterator history
, epoch_t epoch
);
112 CephContext
*const cct
;
113 Puller
*const puller
; //< interface for pulling missing periods
114 Cursor current_cursor
; //< Cursor to realm's current period
116 mutable std::mutex mutex
; //< protects the histories
118 /// set of disjoint histories that are missing intermediate periods needed to
119 /// connect them together
122 /// iterator to the history that contains the realm's current period
123 Set::const_iterator current_history
;
126 RGWPeriodHistory::Impl::Impl(CephContext
* cct
, Puller
* puller
,
127 const RGWPeriod
& current_period
)
128 : cct(cct
), puller(puller
)
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
);
135 // insert as our current history
136 current_history
= histories
.insert(*history
).first
;
138 // get a cursor to the current period
139 current_cursor
= make_cursor(current_history
, current_period
.get_realm_epoch());
141 current_history
= histories
.end();
145 RGWPeriodHistory::Impl::~Impl()
147 // clear the histories and delete each entry
148 histories
.clear_and_dispose(std::default_delete
<History
>{});
151 Cursor
RGWPeriodHistory::Impl::attach(RGWPeriod
&& period
, optional_yield y
)
153 if (current_history
== histories
.end()) {
154 return Cursor
{-EINVAL
};
157 const auto epoch
= period
.get_realm_epoch();
159 std::string predecessor_id
;
162 // hold the lock over insert, and while accessing the unsafe cursor
163 std::lock_guard
<std::mutex
> lock(mutex
);
165 auto cursor
= insert_locked(std::move(period
));
169 if (current_history
->contains(epoch
)) {
170 break; // the history is complete
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();
177 predecessor_id
= current_history
->get_predecessor_id();
181 if (predecessor_id
.empty()) {
182 lderr(cct
) << "reached a period with an empty predecessor id" << dendl
;
183 return Cursor
{-EINVAL
};
186 // pull the period outside of the lock
187 int r
= puller
->pull(predecessor_id
, period
, y
);
193 // return a cursor to the requested period
194 return make_cursor(current_history
, epoch
);
197 Cursor
RGWPeriodHistory::Impl::insert(RGWPeriod
&& period
)
199 if (current_history
== histories
.end()) {
200 return Cursor
{-EINVAL
};
203 std::lock_guard
<std::mutex
> lock(mutex
);
205 auto cursor
= insert_locked(std::move(period
));
207 if (cursor
.get_error()) {
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
) {
219 Cursor
RGWPeriodHistory::Impl::lookup(epoch_t realm_epoch
)
221 if (current_history
!= histories
.end() &&
222 current_history
->contains(realm_epoch
)) {
223 return make_cursor(current_history
, realm_epoch
);
228 Cursor
RGWPeriodHistory::Impl::insert_locked(RGWPeriod
&& period
)
230 auto epoch
= period
.get_realm_epoch();
232 // find the first history whose newest epoch comes at or after this period
233 auto i
= histories
.lower_bound(epoch
, NewestEpochLess
{});
235 if (i
== histories
.end()) {
236 // epoch is past the end of our newest history
237 auto last
= --Set::iterator
{i
}; // last = i - 1
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
);
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
);
250 i
= Set::s_iterator_to(*history
);
251 return make_cursor(i
, epoch
);
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
};
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
);
268 return make_cursor(i
, epoch
);
271 if (epoch
+ 1 == i
->get_oldest_epoch()) {
272 // insert at the front of this history
273 i
->periods
.emplace_front(std::move(period
));
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) {
282 return make_cursor(i
, epoch
);
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
);
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
);
299 i
= Set::s_iterator_to(*history
);
300 return make_cursor(i
, epoch
);
303 RGWPeriodHistory::Impl::Set::iterator
304 RGWPeriodHistory::Impl::merge(Set::iterator dst
, Set::iterator src
)
306 ceph_assert(dst
->get_newest_epoch() + 1 == src
->get_oldest_epoch());
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
>{});
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
>{});
326 Cursor
RGWPeriodHistory::Impl::make_cursor(Set::const_iterator history
,
328 return Cursor
{&*history
, &mutex
, epoch
};
332 RGWPeriodHistory::RGWPeriodHistory(CephContext
* cct
, Puller
* puller
,
333 const RGWPeriod
& current_period
)
334 : impl(new Impl(cct
, puller
, current_period
)) {}
336 RGWPeriodHistory::~RGWPeriodHistory() = default;
338 Cursor
RGWPeriodHistory::get_current() const
340 return impl
->get_current();
342 Cursor
RGWPeriodHistory::attach(RGWPeriod
&& period
, optional_yield y
)
344 return impl
->attach(std::move(period
), y
);
346 Cursor
RGWPeriodHistory::insert(RGWPeriod
&& period
)
348 return impl
->insert(std::move(period
));
350 Cursor
RGWPeriodHistory::lookup(epoch_t realm_epoch
)
352 return impl
->lookup(realm_epoch
);