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"
8 #include "include/ceph_assert.h"
10 #define dout_subsys ceph_subsys_rgw
13 #define dout_prefix (*_dout << "rgw period history: ")
15 /// an ordered history of consecutive periods
16 class RGWPeriodHistory::History
: public bi::avl_set_base_hook
<> {
18 std::deque
<RGWPeriod
> periods
;
20 epoch_t
get_oldest_epoch() const {
21 return periods
.front().get_realm_epoch();
23 epoch_t
get_newest_epoch() const {
24 return periods
.back().get_realm_epoch();
26 bool contains(epoch_t epoch
) const {
27 return get_oldest_epoch() <= epoch
&& epoch
<= get_newest_epoch();
29 RGWPeriod
& get(epoch_t epoch
) {
30 return periods
[epoch
- get_oldest_epoch()];
32 const RGWPeriod
& get(epoch_t epoch
) const {
33 return periods
[epoch
- get_oldest_epoch()];
35 const std::string
& get_predecessor_id() const {
36 return periods
.front().get_predecessor();
40 /// value comparison for avl_set
41 bool operator<(const RGWPeriodHistory::History
& lhs
,
42 const RGWPeriodHistory::History
& rhs
)
44 return lhs
.get_newest_epoch() < rhs
.get_newest_epoch();
47 /// key-value comparison for avl_set
48 struct NewestEpochLess
{
49 bool operator()(const RGWPeriodHistory::History
& value
, epoch_t key
) const {
50 return value
.get_newest_epoch() < key
;
55 using Cursor
= RGWPeriodHistory::Cursor
;
57 const RGWPeriod
& Cursor::get_period() const
59 std::lock_guard
<std::mutex
> lock(*mutex
);
60 return history
->get(epoch
);
62 bool Cursor::has_prev() const
64 std::lock_guard
<std::mutex
> lock(*mutex
);
65 return epoch
> history
->get_oldest_epoch();
67 bool Cursor::has_next() const
69 std::lock_guard
<std::mutex
> lock(*mutex
);
70 return epoch
< history
->get_newest_epoch();
73 bool operator==(const Cursor
& lhs
, const Cursor
& rhs
)
75 return lhs
.history
== rhs
.history
&& lhs
.epoch
== rhs
.epoch
;
78 bool operator!=(const Cursor
& lhs
, const Cursor
& rhs
)
83 class RGWPeriodHistory::Impl final
{
85 Impl(CephContext
* cct
, Puller
* puller
, const RGWPeriod
& current_period
);
88 Cursor
get_current() const { return current_cursor
; }
89 Cursor
attach(RGWPeriod
&& period
);
90 Cursor
insert(RGWPeriod
&& period
);
91 Cursor
lookup(epoch_t realm_epoch
);
94 /// an intrusive set of histories, ordered by their newest epoch. although
95 /// the newest epoch of each history is mutable, the ordering cannot change
96 /// because we prevent the histories from overlapping
97 using Set
= bi::avl_set
<RGWPeriodHistory::History
>;
99 /// insert the given period into the period history, creating new unconnected
100 /// histories or merging existing histories as necessary. expects the caller
101 /// to hold a lock on mutex. returns a valid cursor regardless of whether it
102 /// ends up in current_history, though cursors in other histories are only
103 /// valid within the context of the lock
104 Cursor
insert_locked(RGWPeriod
&& period
);
106 /// merge the periods from the src history onto the end of the dst history,
107 /// and return an iterator to the merged history
108 Set::iterator
merge(Set::iterator dst
, Set::iterator src
);
110 /// construct a Cursor object using Cursor's private constuctor
111 Cursor
make_cursor(Set::const_iterator history
, epoch_t epoch
);
113 CephContext
*const cct
;
114 Puller
*const puller
; //< interface for pulling missing periods
115 Cursor current_cursor
; //< Cursor to realm's current period
117 mutable std::mutex mutex
; //< protects the histories
119 /// set of disjoint histories that are missing intermediate periods needed to
120 /// connect them together
123 /// iterator to the history that contains the realm's current period
124 Set::const_iterator current_history
;
127 RGWPeriodHistory::Impl::Impl(CephContext
* cct
, Puller
* puller
,
128 const RGWPeriod
& current_period
)
129 : cct(cct
), puller(puller
)
131 if (!current_period
.get_id().empty()) {
132 // copy the current period into a new history
133 auto history
= new History
;
134 history
->periods
.push_back(current_period
);
136 // insert as our current history
137 current_history
= histories
.insert(*history
).first
;
139 // get a cursor to the current period
140 current_cursor
= make_cursor(current_history
, current_period
.get_realm_epoch());
142 current_history
= histories
.end();
146 RGWPeriodHistory::Impl::~Impl()
148 // clear the histories and delete each entry
149 histories
.clear_and_dispose(std::default_delete
<History
>{});
152 Cursor
RGWPeriodHistory::Impl::attach(RGWPeriod
&& period
)
154 if (current_history
== histories
.end()) {
155 return Cursor
{-EINVAL
};
158 const auto epoch
= period
.get_realm_epoch();
160 std::string predecessor_id
;
163 // hold the lock over insert, and while accessing the unsafe cursor
164 std::lock_guard
<std::mutex
> lock(mutex
);
166 auto cursor
= insert_locked(std::move(period
));
170 if (current_history
->contains(epoch
)) {
171 break; // the history is complete
174 // take the predecessor id of the most recent history
175 if (cursor
.get_epoch() > current_cursor
.get_epoch()) {
176 predecessor_id
= cursor
.history
->get_predecessor_id();
178 predecessor_id
= current_history
->get_predecessor_id();
182 if (predecessor_id
.empty()) {
183 lderr(cct
) << "reached a period with an empty predecessor id" << dendl
;
184 return Cursor
{-EINVAL
};
187 // pull the period outside of the lock
188 int r
= puller
->pull(predecessor_id
, period
);
194 // return a cursor to the requested period
195 return make_cursor(current_history
, epoch
);
198 Cursor
RGWPeriodHistory::Impl::insert(RGWPeriod
&& period
)
200 if (current_history
== histories
.end()) {
201 return Cursor
{-EINVAL
};
204 std::lock_guard
<std::mutex
> lock(mutex
);
206 auto cursor
= insert_locked(std::move(period
));
208 if (cursor
.get_error()) {
211 // we can only provide cursors that are safe to use outside of the mutex if
212 // they're within the current_history, because other histories can disappear
213 // in a merge. see merge() for the special handling of current_history
214 if (cursor
.history
== &*current_history
) {
220 Cursor
RGWPeriodHistory::Impl::lookup(epoch_t realm_epoch
)
222 if (current_history
!= histories
.end() &&
223 current_history
->contains(realm_epoch
)) {
224 return make_cursor(current_history
, realm_epoch
);
229 Cursor
RGWPeriodHistory::Impl::insert_locked(RGWPeriod
&& period
)
231 auto epoch
= period
.get_realm_epoch();
233 // find the first history whose newest epoch comes at or after this period
234 auto i
= histories
.lower_bound(epoch
, NewestEpochLess
{});
236 if (i
== histories
.end()) {
237 // epoch is past the end of our newest history
238 auto last
= --Set::iterator
{i
}; // last = i - 1
240 if (epoch
== last
->get_newest_epoch() + 1) {
241 // insert at the back of the last history
242 last
->periods
.emplace_back(std::move(period
));
243 return make_cursor(last
, epoch
);
246 // create a new history for this period
247 auto history
= new History
;
248 history
->periods
.emplace_back(std::move(period
));
249 histories
.insert(last
, *history
);
251 i
= Set::s_iterator_to(*history
);
252 return make_cursor(i
, epoch
);
255 if (i
->contains(epoch
)) {
256 // already resident in this history
257 auto& existing
= i
->get(epoch
);
258 // verify that the period ids match; otherwise we've forked the history
259 if (period
.get_id() != existing
.get_id()) {
260 lderr(cct
) << "Got two different periods, " << period
.get_id()
261 << " and " << existing
.get_id() << ", with the same realm epoch "
262 << epoch
<< "! This indicates a fork in the period history." << dendl
;
263 return Cursor
{-EEXIST
};
265 // update the existing period if we got a newer period epoch
266 if (period
.get_epoch() > existing
.get_epoch()) {
267 existing
= std::move(period
);
269 return make_cursor(i
, epoch
);
272 if (epoch
+ 1 == i
->get_oldest_epoch()) {
273 // insert at the front of this history
274 i
->periods
.emplace_front(std::move(period
));
276 // try to merge with the previous history
277 if (i
!= histories
.begin()) {
278 auto prev
= --Set::iterator
{i
};
279 if (epoch
== prev
->get_newest_epoch() + 1) {
283 return make_cursor(i
, epoch
);
286 if (i
!= histories
.begin()) {
287 auto prev
= --Set::iterator
{i
};
288 if (epoch
== prev
->get_newest_epoch() + 1) {
289 // insert at the back of the previous history
290 prev
->periods
.emplace_back(std::move(period
));
291 return make_cursor(prev
, epoch
);
295 // create a new history for this period
296 auto history
= new History
;
297 history
->periods
.emplace_back(std::move(period
));
298 histories
.insert(i
, *history
);
300 i
= Set::s_iterator_to(*history
);
301 return make_cursor(i
, epoch
);
304 RGWPeriodHistory::Impl::Set::iterator
305 RGWPeriodHistory::Impl::merge(Set::iterator dst
, Set::iterator src
)
307 ceph_assert(dst
->get_newest_epoch() + 1 == src
->get_oldest_epoch());
309 // always merge into current_history
310 if (src
== current_history
) {
311 // move the periods from dst onto the front of src
312 src
->periods
.insert(src
->periods
.begin(),
313 std::make_move_iterator(dst
->periods
.begin()),
314 std::make_move_iterator(dst
->periods
.end()));
315 histories
.erase_and_dispose(dst
, std::default_delete
<History
>{});
319 // move the periods from src onto the end of dst
320 dst
->periods
.insert(dst
->periods
.end(),
321 std::make_move_iterator(src
->periods
.begin()),
322 std::make_move_iterator(src
->periods
.end()));
323 histories
.erase_and_dispose(src
, std::default_delete
<History
>{});
327 Cursor
RGWPeriodHistory::Impl::make_cursor(Set::const_iterator history
,
329 return Cursor
{&*history
, &mutex
, epoch
};
333 RGWPeriodHistory::RGWPeriodHistory(CephContext
* cct
, Puller
* puller
,
334 const RGWPeriod
& current_period
)
335 : impl(new Impl(cct
, puller
, current_period
)) {}
337 RGWPeriodHistory::~RGWPeriodHistory() = default;
339 Cursor
RGWPeriodHistory::get_current() const
341 return impl
->get_current();
343 Cursor
RGWPeriodHistory::attach(RGWPeriod
&& period
)
345 return impl
->attach(std::move(period
));
347 Cursor
RGWPeriodHistory::insert(RGWPeriod
&& period
)
349 return impl
->insert(std::move(period
));
351 Cursor
RGWPeriodHistory::lookup(epoch_t realm_epoch
)
353 return impl
->lookup(realm_epoch
);